Dynamic Programming I: The Grammar

1The same work, over and over

Write Fibonacci the obvious way and it takes exponential time. Nothing is wrong with the logic. Everything is wrong with the repetition.

Here is the canonical example. The recursion is a direct transcription of the mathematical definition, and it is correct:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Count the calls: fib(5) makes 15, fib(30) makes about 2.7 million, and fib(50) would take roughly a day. The tree has O(φⁿ) nodes but only n + 1 distinct questions in it. Everything past the first occurrence of each is waste.

2Memoisation: write it down

Keep a dictionary of answers you have already computed. Two lines, and the exponential collapses.

The fix requires no new insight at all. Before doing the work, check whether you already did it:

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:                        # <-- have we been asked this before?
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)   # <-- write it down
    return memo[n]

Python ships this as a decorator, and in real code that is what you would use:

from functools import lru_cache

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

3The four blanks

Every DP solution is the same four sentences. Write them in English before you write any code, and the code becomes transcription.

People describe DP as requiring a flash of insight. It does not. It requires filling in a form:

The running time then follows arithmetically, with no cleverness required:

time = (number of states) × (cost of one transition)

Fibonacci: n states, O(1) each, so O(n). Coin change with amount A and c coins: A states, c per transition, so O(A·c). Edit distance on strings of length n and m: n·m states, O(1) each. You can quote the complexity before writing a line.

4Top-down or bottom-up

The same recurrence, computed in two directions. They are equivalent in what they compute and very different to work with.

Top-down (memoisation) starts at the answer you want and recurses down, caching. Bottom-up (tabulation) starts at the base cases and fills a table forward until it reaches the answer.

# Top-down: recursion + cache. Follows the definition literally.
def coins_td(coins, amount, memo=None):
    if memo is None:
        memo = {}
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    if amount in memo:
        return memo[amount]
    memo[amount] = min((coins_td(coins, amount - c, memo) + 1 for c in coins),
                       default=float("inf"))
    return memo[amount]


# Bottom-up: a loop and an array. No stack, and the order is explicit.
def coins_bu(coins, amount):
    dp = [0] + [float("inf")] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount]

5Less memory, and the actual answer

Two refinements that turn a working DP into a usable one.

Rolling the table. If dp[i] depends only on dp[i-1] and dp[i-2], there is no reason to keep the other n - 2 entries:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

The same trick applies to 2-D tables whose rows depend only on the previous row: keep two rows instead of n, and edit distance drops from O(n·m) memory to O(m). On large inputs this is often the difference between running and not.

Reconstruction. Two approaches, both common:

# 1. Store a back-pointer alongside each answer.
def min_coins_with_list(coins, amount):
    dp = [0] + [float("inf")] * amount
    take = [None] * (amount + 1)              # which coin produced dp[x]
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
                take[x] = c
    if dp[amount] == float("inf"):
        return None
    out, x = [], amount
    while x > 0:
        out.append(take[x])
        x -= take[x]

    return out


# 2. Or keep the full table and walk backwards, re-deriving each choice.
#    No extra memory, slightly more thinking at the end.

6DP, greedy, and divide-and-conquer

Three paradigms that all break a problem into smaller ones. What separates them is how the pieces relate.

The practical decision procedure, in order:

1. Can I make a local choice and prove it safe? If yes, greedy — it is faster and shorter. Chapter 24 is about how to check.
2. Do the subproblems repeat? If yes, DP. If no, plain divide-and-conquer or recursion is enough.
3. Is the state space too big to tabulate? Then backtracking with pruning (Chapter 27), or an approximation.

And a warning about the reverse direction. Not everything that looks like DP is: if the subproblems do not actually overlap, you have paid for a table you did not need. Check that the number of distinct states is genuinely smaller than the number of calls before reaching for a cache.

>_Playground

Count the calls, watch memoisation collapse them, and compare top-down with bottom-up on the same recurrence.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.