Dynamic Programming Basics

What dynamic programming is

Dynamic programming (DP for short) is a way of solving a problem by breaking it into smaller versions of the same problem, solving each smaller version once, and reusing those answers instead of recomputing them.

The name is historical and a little misleading. It has nothing to do with the modern sense of “dynamic.” Think of it as “careful recursion that remembers.”

DP is worth learning because it turns some problems that look impossibly slow (they would take longer than the age of the universe on a medium input) into problems a laptop solves instantly. The speedup comes from one idea: stop redoing work you have already done.

Before we go further, two definitions we will use constantly:

• Recursion: a function that calls itself on a smaller input. A problem “solved recursively” is defined in terms of smaller copies of itself.
• Subproblem: one of those smaller copies. If the big problem is “the 10th Fibonacci number,” a subproblem is “the 7th Fibonacci number.”

The two properties a problem needs

DP does not apply to every problem. It applies when the problem has both of these:

Overlapping subproblems

The same smaller subproblem shows up many times while solving the big one. This is the property that makes remembering pay off. If every subproblem were unique, there would be nothing to reuse.

Optimal substructure

The best answer to the big problem can be built out of the best answers to its subproblems. For example, the cheapest way to make 11 cents can be built from the cheapest way to make some smaller amount plus one more coin. If knowing the best sub-answers is enough to construct the best full answer, the problem has optimal substructure.

If both hold, DP works. If only overlapping subproblems hold (no “best” is involved, you just want the count or the value), DP still works to speed things up. The “optimal substructure” property matters specifically when you are optimizing (minimum, maximum, fewest, cheapest).

Fibonacci: the clearest example of overlapping subproblems

The Fibonacci sequence is: each number is the sum of the two before it.

index:  0  1  2  3  4  5  6  7
value:  0  1  1  2  3  5  8  13

The rule, written as a recurrence (a formula that defines a value in terms of smaller values of itself):

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)   for n >= 2

The two lines that do not refer to anything smaller (fib(0) and fib(1)) are the base cases: the points where recursion stops. Every recursion needs base cases or it calls itself forever.

Here is the direct translation into Python:

def fib(n):
    if n < 2:          # base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # -> 55

This is correct, but it is catastrophically slow for larger n. To see why, look at what it actually computes.

When you ask for fib(5), it asks for fib(4) and fib(3). Each of those asks for two more, and so on. The calls form a tree:

graph TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    F2a --> F1c["fib(1)"]
    F2a --> F0a["fib(0)"]
    F2b --> F1d["fib(1)"]
    F2b --> F0b["fib(0)"]
    F2c --> F1e["fib(1)"]
    F2c --> F0c["fib(0)"]

Look at how many times the same box appears. fib(3) is computed twice, fib(2) three times, fib(1) five times. Those are the overlapping subproblems. The tree roughly doubles in size each level, so the number of calls grows like 2^n.

• Time: O(2^n) — exponential. fib(50) would make over a billion calls.
• Space: O(n) — the depth of the deepest path in the tree (how many calls are stacked up at once).

O(2^n) means the work doubles every time n grows by one, and that exponential growth is exactly what DP eliminates.

Technique 1: memoization (top-down)

Memoization means storing the result of each subproblem the first time you compute it, then returning the stored value if you are ever asked again. “Memo” as in a note to self. It is called top-down because you still start from the big problem (fib(n)) and recurse down to the base cases, exactly like before, but with a cache in front.

We store results in a dictionary (a Python structure that maps a key to a value, here mapping n to fib(n)).

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:          # already solved this subproblem? return the stored answer
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(10))   # -> 55
print(fib(50))   # -> 12586269025   (instant, not billions of calls)

Now each distinct fib(k) is computed once. The second time the tree wants fib(3), it is already in memo and returns immediately. The tree collapses into a thin line.

• Time: O(n) — there are only n distinct subproblems, each done once.
• Space: O(n) — the memo dictionary holds n answers, plus O(n) recursion depth.

We went from O(2^n) to O(n). For fib(50) that is the difference between a billion operations and about fifty.

Note the memo=None then memo = {} pattern. Do not write def fib(n, memo={}) directly. A default argument like {} is created once and shared across all calls, which causes stale data to leak between separate calls. Building a fresh dictionary inside the function avoids that trap.

Technique 2: tabulation (bottom-up)

Tabulation solves the same problem from the other direction. Instead of starting at fib(n) and recursing down, you start at the base cases and build up, filling a list (a “table”) from the smallest subproblem to the largest. No recursion at all, just a loop.

The table is usually an array called dp, where dp[i] holds the answer to subproblem i.

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)   # a list of n+1 zeros: dp[0]..dp[n]
    dp[0] = 0            # base case
    dp[1] = 1            # base case
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # fill using values already computed
    return dp[n]

print(fib(10))   # -> 55

• Time: O(n) — one pass filling n cells, constant work per cell.
• Space: O(n) — the dp list.

Filling the table is the heart of DP. Each row below shows the dp list right after that step’s cell is filled. Computing fib(6):

The answer is dp[6] = 8. Notice each new cell only needs cells already filled to its left. That is why we walk left to right: a cell’s inputs must exist before we use them. Filling in the wrong order would read an empty cell and give a wrong answer.

Memoization vs tabulation

Both give the same answer and the same Big-O for Fibonacci. Memoization is often easier to write first because it is just your recursion plus a cache. Tabulation is often easier to reason about for space and avoids recursion limits.

How to find the recurrence

The recurrence is the formula at the center of every DP. Finding it is the real skill. A repeatable process:

1. Define the subproblem in words. Decide precisely what dp[i] (or dp[i][j]) means. For Fibonacci: “dp[i] is the i-th Fibonacci number.” Vague definitions produce wrong recurrences, so make this a full sentence.
2. Write the recurrence: express dp[i] using smaller entries. Ask “if I already knew all the smaller answers, how would I combine them to get this one?” For Fibonacci: dp[i] = dp[i-1] + dp[i-2].
3. Nail the base cases. The smallest inputs that have a direct answer with no recursion. For Fibonacci: dp[0] = 0, dp[1] = 1.
4. Decide the fill order. Every entry must be filled after the entries it depends on. Fibonacci depends on smaller indices, so fill from small to large.

Worked example: climbing stairs

A staircase has n steps. You can climb either 1 step or 2 steps at a time. How many distinct ways can you reach the top?

Apply the four questions:

1. Subproblem: dp[i] = the number of distinct ways to reach step i.
2. Recurrence: to arrive at step i, your last move was either a 1-step (from i-1) or a 2-step (from i-2). So every way of reaching i-1 and every way of reaching i-2 becomes a way of reaching i: dp[i] = dp[i-1] + dp[i-2].
3. Base cases: dp[0] = 1 (one way to “be” at the ground: do nothing) and dp[1] = 1 (one way to reach step 1: a single 1-step).
4. Fill order: small to large.

(The recurrence is the same shape as Fibonacci. That is common. Many different-sounding problems share a recurrence.)

def climb_stairs(n):
    if n < 2:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(5))   # -> 8

• Time: O(n), Space: O(n).

Table trace for n = 5:

There are 8 ways to climb 5 steps.

Saving space

Notice dp[i] only ever reads the two cells before it. You never look further back, so you do not need the whole list, just the last two values:

def climb_stairs(n):
    prev, curr = 1, 1        # ways to reach step 0 and step 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

print(climb_stairs(5))   # -> 8

• Time: O(n), Space: O(1) — constant space, only two variables.

This “rolling variables” trick works whenever each entry depends only on a fixed number of recent entries. It does not change the time, only the memory.

A second recurrence shape: coin change

Some DP problems optimize (fewest, most, cheapest) rather than count. This is where optimal substructure earns its keep.

Problem: given coin values [1, 3, 4] and a target amount, what is the fewest coins that sum exactly to amount? (You have unlimited coins of each value.)

1. Subproblem: dp[a] = the fewest coins needed to make amount a.
2. Recurrence: to make amount a, the last coin you added was some coin c from the list. Before that coin, you had made amount a - c, which took dp[a - c] coins at best. Try every coin and take the smallest result: dp[a] = 1 + min(dp[a - c] for each coin c where c <= a). This is optimal substructure: the best way to make a is built from the best way to make a smaller amount.
3. Base case: dp[0] = 0 (zero coins make amount 0).
4. Fill order: small amounts to large, because dp[a] needs smaller dp values.

We seed the unknown cells with infinity to mean “not reachable yet,” so min never picks an unfilled cell.

def coin_change(coins, amount):
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0                          # base case
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1   # -1 = impossible

print(coin_change([1, 3, 4], 6))   # -> 2   (3 + 3)
print(coin_change([2], 3))         # -> -1  (cannot make 3 from only 2s)

• Time: O(amount * number_of_coins) — for each of amount cells we try every coin.
• Space: O(amount) — the dp list.

Table trace for coins = [1, 3, 4], amount = 6. Each cell is 1 + min over the reachable coins:

dp[6] = 2, matching 3 + 3. Watch how dp[3] dropping to 1 (using a single 3-coin) later makes dp[6] cheap: earlier good sub-answers feed later ones. That is optimal substructure in motion.

Complexity: the whole point

The derivation in one line: plain recursion recomputes each overlapping subproblem an exponential number of times; DP computes each distinct subproblem exactly once, so the total time equals the number of distinct subproblems times the work per subproblem. Count your distinct subproblems and you have your time bound.

Common pitfalls

• Wrong or missing base cases. The base cases anchor everything built on top. A Fibonacci dp[0] set to 1 instead of 0 poisons every later cell. Always verify the smallest inputs by hand.
• Wrong iteration order. A cell must be filled after everything it reads. If you loop from large to small when the recurrence looks backward, you read empty (or stale) cells. Match the loop direction to the dependency direction.
• Off-by-one in table size. To store dp[0] through dp[n] you need a list of length n + 1, not n. [0] * n leaves no room for dp[n] and raises an IndexError.
• Mutable default argument. def f(n, memo={}) shares one dictionary across all calls, leaking answers between unrelated inputs. Use memo=None and create a fresh dict inside.
• Forgetting the “impossible” case. In coin change, an unreachable amount stays infinity. Return a sentinel like -1 for it instead of a nonsense huge number.
• Recursion depth with memoization. Top-down on a very large n can exceed Python’s recursion limit and crash. Tabulation avoids this since it uses a loop.

Practice

1. Minimum path in a grid. Given a grid of numbers where you may move only right or down, find the smallest sum from the top-left to the bottom-right cell. Define dp[r][c] as the cheapest cost to reach cell (r, c), write the recurrence, and fill the table.
2. House robber. Given a list of house values, pick a subset with the largest total such that no two picked houses are adjacent. Define dp[i] as the best total considering the first i houses, and find the recurrence relating dp[i] to dp[i-1] and dp[i-2].
3. Rewrite coin change top-down. Convert the coin-change tabulation above into a memoized recursive version. Confirm it returns the same answers for ([1, 3, 4], 6) and ([2], 3).