Dynamic Programming Demystified

Dynamic Programming (DP) is a powerful technique used to solve problems that involve making a sequence of decisions, often with overlapping sub problems. It’s widely regarded as a challenging concept, but with the right approach, it becomes a highly effective tool in an algorithmic toolbox. Whether you’re solving optimization problems, finding the shortest path, or tackling knapsack-style problems, DP can simplify what would otherwise be complicated recursive algorithms.

In this blog, we’ll demystify Dynamic Programming by breaking it down into simple concepts, showing how to identify DP problems, and providing step-by-step explanations of classic DP solutions. By the end, you’ll have a solid understanding of how to approach and solve problems using DP with confidence.

1/ Introduction

When I first started learning Dynamic Programming (DP), it honestly felt like magic. I’d look at problems and have no idea where to begin. I’d watch tutorials or read blog posts where people just seemed to “know” the subproblems and somehow come up with the recurrence relation like it was obvious—and I’d just sit there wondering, how ton earth did they come up with that? It all felt overwhelming, and no matter how many solutions I saw, I couldn’t connect the dots or apply the same ideas on my own.

Take the classic “Coin Change” problem, for example. I remember staring at the problem statement thinking, “Okay, I need to make up an amount using the fewest coins possible… sounds simple enough.” But once I started thinking about how to actually solve it, I hit a wall. Should I go with recursion? Try all combinations? How do I avoid repeating work? Then I’d look at someone else’s solution, and they’d just magically come up with a one-dimensional DP array and a few neat for-loops that somehow solve everything. And I’d be sitting there thinking: How did they even know to build that array? Why that loop order? Why that formular? It felt like I was missing some secret rule everyone else had.

2/ Method

But then, after reading and truly understanding a few solutions—not just copying them—I started noticing a pattern in how people approached DP. It wasn’t magic after all; there was a method to the madness. I realized that solving DP problems is like solving a puzzle with a process.

“The Root of Dynamic Programming is about math and patterns. Not Coding”

1. Test cases – Start with tiny inputs like 1, 2, or 3 and manually work out the answer. It helps build intuition.

2. Pattern – See how the result for a larger case depends on smaller ones. Ask yourself: “What decisions did I make? What repeated?”

3. Formula – Once you notice how smaller results combine, try expressing it as a recurrence relation or formula.

4. Code – Now that you understand the logic, write the actual DP code, starting with recursion or bottom-up as needed.

3/ Examples

Climbing Stairs Problem:

You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. Determine the number of distinct ways to reach the top.

Example: Input: n = 3, Output: 3 (Ways: [1,1,1], [1,2], [2,1])

1. Test cases

2. Pattern

Notice the pattern in the number of ways to reach the top for each n: 1, 2, 3, 5, 8, 13, …

This sequence is very similar to the Fibonacci sequence, where each number is the sum of the two preceding numbers. In fact, it’s a shifted version of the Fibonacci sequence. The Fibonacci sequence is defined as:

$$F(n) = F(n-1) + F(n-2)$$

3. Formula

$$ways(n) = F(n-1) + F(n-2)$$

Where F(n) is the n-th Fibonacci number.

4. Code

def solve(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2

    ways = [1,2]
    i = 2
    while i < n:
        ways.append(ways[i-2]+ways[i-1]) 
        i += 1
    return ways[-1]

n = 3
print(solve(n)) # Output: 3

Coin change problem

Given an array coins representing coin denominations and an integer amount, determine the minimum number of coins needed to make up amount. If it is not possible, return -1.

Example: Input: coins = [1,2,5], amount = 11, Output: 3 (using [5,5,1])

1. Test Cases

Let’s say we haveCoins = {1, 2, 3}, amount T = 5, we have a 1-D array amounts to store minimum number of coins to form a specific amount ranging from 0 to T. We intitialize amounts with ∞ values.

2. Pattern

Notice the pattern in the number of coins to form a target amount T = 5 when using coins {1, 2, 3}:

Coin = 1: The number of coins to form each amount is 1. This is because we can only use the coin 1, so for coin equals to 1:* amounts = [0, 1, 2, 3, 4, 5]

Coin = 2: The number of coins to form each amount increases as we can now use both coin 1 and coin 2. For each amount t, we see that:*

amounts[1] = 1 (We took the amount from amounts where coin = 1

amounts[2] \= amounts[2-2] + 1 \= 1 ( < amounts[2] where coin = 1 )

amounts[3] \= amounts[3-2] + 1 \= 2 ( < amounts[3] where coin = 1 )

amounts[4] \= amounts[4-2] + 1 = 2 ( < amounts[4] where coin = 1 )

amounts[5] \= amounts[5-2] + 1 = 3 ( < amounts[5] where coin = 1 )

Coin = 3: The number of ways to form each amount increases as we can now use both coin 1, coin 2 and coin 3. For each amount t, we see that:*

amounts[1] = 1 (We took the amount from amounts where coin = 2

amounts[2] = 1 (We took the amount from amounts where coin = 2

amounts[3] = amounts[3-3] + 1 \= 1 ( < amounts[3-2] + 1 )

amounts[4] = amounts[4-3] + 1 \= 2

amounts[5] = amounts[5-3] + 1 \= 2 ( < amounts[5-2] + 1 )

3. Formula

$$amounts[i] = min(amounts[i], amounts[i-coin] + 1)$$

Where amounts[i] is the number of ways to form a specific amount of coins, coin is a specific coin from the input. We use min() because we are trying to find the fewest number of coins needed to make up the amount i by updating 1-D amounts array at index i.

4. Code

def solve(coins, amount):

    amounts = [float('inf')] * (amount+1) 
    amounts[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin: 
                amounts[i] = min(amounts[i], amounts[i-coin] + 1) 

    return amounts[amount] if amounts[amount] != float('inf') else -1

coins = [1,2,5]
amount = 11
print(solve(coins,amount)) # Output: 3 (Using [5,5,1])

4/ Conclusion

Dynamic Programming is a powerful technique for solving problems that can be broken down into overlapping sub problems with optimal substructure.

In this blog, we explored DP through classic problems like Climbing Stairs and Coin Change, learning how to:

• Identify the sub problem patterns

• Define a formula

• Use bottom-up approaches

The key takeaway is: Always look for pattern before coding**.** Once you identify those, DP becomes a game of defining a state and filling up a table.