Dynamic Programming Fundamentals

Overlapping Subproblems

The textbook recursive definition of Fibonacci translates directly into code, exactly Lesson 5's recursion pattern, base case and recursive case:

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

print(fib_naive(20))

6765

Every call is a node in a tree, and the waste is obvious once it is drawn. Each fib(k) spawns fib(k-1) and fib(k-2), so the same subproblems reappear all over the tree. The two amber fib(3) subtrees below are identical, yet the naive version computes both from scratch:

Memoization: Top-Down DP

The fix is almost mechanical: keep a cache of subproblems already solved, and check it before recursing. This is called memoization, still top-down (it starts from n and recurses toward the base case, same call structure as before), but now each distinct subproblem is computed exactly once:

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]           # already solved this subproblem, skip the recursion entirely
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(50))

12586269025

With only n distinct subproblems and O(1) work per subproblem (one addition, one cache lookup), this drops from O(2ⁿ) to O(n), instant even for n = 50, where the naive version would still be running. Python's functools.lru_cache does the exact same thing automatically, no manual dictionary required:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n: int) -> int:
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

print(fib_cached(50))

12586269025

Tabulation: Bottom-Up DP

Memoization still recurses, working down from n until it hits a base case. Tabulation flips the direction: start from the base cases and iteratively build up to n, filling a table in order instead of recursing:

def fib_tabulated(n: int) -> int:
    if n <= 1:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

print(fib_tabulated(50))

12586269025

Same O(n) time as memoization, but with no recursive call stack at all, just a loop. Since each step of Fibonacci only ever needs the previous two values, the full table array isn't even necessary, tracking just two running values instead of the whole table brings the space down from O(n) to O(1), a common next step once a tabulated solution is working correctly.

Solving Lesson 17's Coin Change Correctly

Lesson 17 showed that greedily grabbing the largest coin fails for denominations [1, 3, 4]: it finds a 3-coin solution for the amount 6, when a 2-coin solution exists. DP solves this by computing the true minimum for every smaller amount first, then reusing those answers: the fewest coins for amount a is 1 + the fewest coins for a - coin, minimized over every available coin, exactly the optimal substructure property.

def min_coins(amount: int, denominations: list[int]) -> int:
    INF = float("inf")
    table = [0] + [INF] * amount     # table[a] = fewest coins to make amount a
    for a in range(1, amount + 1):
        for coin in denominations:
            if coin <= a and table[a - coin] + 1 < table[a]:
                table[a] = table[a - coin] + 1
    return table[amount] if table[amount] != INF else -1

print(min_coins(6, [1, 3, 4]))
print(min_coins(41, [1, 5, 10, 25]))

2
4

The table array is easier to trust when you can see it. Each column is an amount from 0 to 6, and its cell holds the fewest coins to make that amount with denominations [1, 3, 4]. The answer for 6 sits in the last column. Following the highlighted trail back shows why it is only 2 coins: making 6 reuses the already computed best answer for 3, which in turn reuses the answer for 0, so 6 is built as 3 + 3, exactly the solution greedy missed:

Unlike greedy, which locks in its first choice, this tries every coin at every amount and only keeps the best result, so it can't be fooled the way greedy was. It correctly finds 2 coins for [1, 3, 4] making 6 (the 3 + 3 solution greedy missed) and still gets the right answer, 4 coins, for ordinary US denominations.

Complexity at a Glance

Coin change's table has one entry per amount from 0 to the target, and filling each entry checks every denomination once, giving O(amount × denominations) total work, polynomial, and a world away from trying every possible combination of coins.