Intro to dynamic programming

Why it matters

Some recursive solutions are correct but hopelessly slow because they solve the same smaller problem again and again. Dynamic programming (DP)Solving a problem by solving each smaller sub-problem once and reusing the stored answers. fixes that by solving each sub-problem once and reusing the answer. It powers spell checkers and diff (edit distance), DNA sequence alignment, route planning, resource allocation, and pricing problems. DP has a reputation for being hard, but the beginner version is one idea: remember what you already computed.

The problem: repeated work

From the recursion lesson, the number of ways to climb n stairs taking 1 or 2 steps:

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

Draw the calls for climb(5): it calls climb(4) and climb(3); climb(4) calls climb(3) again and climb(2); and so on. climb(3) is computed twice, climb(2) three times, climb(1) five times. The number of calls roughly doubles each time n goes up by one, about O(2^n). climb(30) makes more than a million calls; climb(80) would not finish in your lifetime.

There are only n + 1 different questions here (climb(0) up to climb(n)). The slowness comes entirely from asking them repeatedly.

Fix 1: memoisation (top-down)

Keep a dictionary of answers. Before computing, check it; after computing, store the result.

def climb(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo)
    return memo[n]

climb(80)   # 37889062373143906, instantly

Each value from 0 to n is computed once, so the time is O(n) with O(n) memory. Python can do this for you with a decorator:

from functools import lru_cache

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

MemoisationTop-down DP: a recursive function stores each answer in a dict and returns the stored value when asked again. keeps the recursive shape, which is often the easiest way to think about the problem. It is still limited by Python's recursion depth (about 1,000).

Fix 2: tabulation (bottom-up)

Instead of starting from n and recursing down, start from the base cases and fill a table upward:

def climb(n):
    ways = [1, 1] + [0] * (n - 1)      # ways[0] = ways[1] = 1
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]

No recursion, no depth limit, same O(n). Since each entry only needs the previous two, you could even keep two variables instead of a list.

Worked example: fewest coins

Given coin values and an amount, what is the fewest coins that make the amount exactly? For coins [1, 3, 4] and amount 6, the greedyAlways taking the locally best choice, such as the biggest coin first, which can miss the overall best answer. choice (take the biggest coin first: 4 + 1 + 1) uses 3 coins, but 3 + 3 uses only 2. Greedy fails; DP does not.

Define best[a] = fewest coins to make amount a. Then best[0] = 0, and for each larger a, try every coin c that fits: best[a] = min(best[a - c] + 1).

def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

min_coins([1, 3, 4], 6)    # 2
min_coins([2], 3)          # -1, impossible
min_coins([5], 0)          # 0

Time is O(amount x number of coins).

A recipe for DP problems

1. Write a brute-force recursive solution and say in words what the function returns.
2. Spot repeated sub-problems. Do different paths of calls ask the same question?
3. Identify the stateThe arguments that define a sub-problem, used as the key for stored answers.: the arguments that define a sub-problem (here just n or a).
4. Memoise on that state. Check correctness against the slow version on small inputs.
5. Optionally convert to a table, filling it in an order where every entry's dependencies come first.

Common mistakes

• Shared mutable defaults like def f(n, memo={}), which leak answers between unrelated calls. Use memo=None and create the dict inside.
• Memoising on the wrong key: if the answer depends on two arguments, the key must include both (a tuple).
• Wrong base cases, such as best[0] set to infinity instead of 0.
• Trusting greedy without checking a counterexample like coins [1, 3, 4].
• Forgetting the impossible case (return -1 or None, and say which).

Quick recap

• DP = solve each sub-problem once and reuse it.
• Memoisation (top-down): recursion plus a dict or lru_cache.
• TabulationBottom-up DP: filling a table from the base cases upward so every entry's dependencies are computed first. (bottom-up): fill a list from the base cases upward.
• Turns exponential recursion like climb into O(n).

Try it

In the Do tab, memoise climb so climb(90) returns instantly, and write min_coins bottom-up. The checks include zero, impossible amounts and a case where greedy is wrong.