Dynamic programming fundamentals

What this chapter covers

Divide and conquer assumed subproblems were independent. Many important problems violate that: their subproblems overlap, the same smaller instance needed again and again, and plain recursion re-solves it exponentially many times. Dynamic programming is the fix, and its whole idea fits in one sentence: compute each distinct subproblem once and remember the answer. That single move — a table, or a cache — turns exponential algorithms into polynomial ones. This chapter builds the paradigm on minimum-coin change (the exact problem greedy failed last chapter — for coins {1,3,4}, greedy makes 6 as 4+1+1 while the optimum is 3+3), showing the same recurrence three ways: naive recursion (exponential), top-down memoization, and bottom-up tabulation. It measures the blowup dynamic programming avoids — at amount 20 the naive version made 641 times more calls than the DP does units of work — and animates the table filling in, the image that makes "remember your subproblems" concrete.

A bit of history

Richard Bellman coined "dynamic programming" in the 1950s at RAND, and the name is famously a bit of misdirection. Bellman was working under a Secretary of Defense who, he wrote, "had a pathological fear and hatred of the word 'research'"; so Bellman picked a name that sounded impressive and impossible to object to — "programming" in the 1950s meant planning/scheduling (as in linear programming), and "dynamic" conveyed time-varying, multistage decisions. The mathematics underneath is his principle of optimality: an optimal solution's tail is itself optimal for the subproblem it faces, which is exactly the "optimal substructure" that makes the recurrence valid. Bellman-Ford (the shortest-path algorithm two tiers back) is his, and it's dynamic programming on graphs. The paradigm turned out to be one of the most broadly applicable in computing — sequence alignment in biology, speech recognition, control theory, reinforcement learning (the Bellman equation is the foundation of Q-learning) — all of it downstream of the insight that overlapping subproblems should be solved once and remembered.

The intuition

Consider computing the naive way. To find the fewest coins for amount a, you try each coin c and recursively find the fewest coins for a − c, taking the best. The recursion is correct but catastrophically wasteful, because the same subamounts recur across different branches: computing the answer for 6 needs the answer for 5, 3, and 2; computing the answer for 5 also needs 2; and so on. The classic illustration is Fibonacci — fib(n) = fib(n-1) + fib(n-2) — where fib(5) computes fib(3) twice, fib(2) three times, fib(1) five times, the recomputation multiplying until the naive algorithm is exponential, O(φⁿ), for a problem that's fundamentally linear. The subproblems overlap, and naive recursion is blind to it.

Dynamic programming makes it not blind. There are two equivalent ways. Top-down memoization keeps the natural recursion but adds a cache: before solving a subproblem, check whether you've solved it before, and if so return the stored answer. Each distinct subproblem is computed once; the rest are lookups. Bottom-up tabulation flips the direction: instead of recursing down from the goal, fill a table starting from the smallest subproblems and building up, each entry using only entries already computed. For coin change, dp[a] = 1 + min over coins c of dp[a-c], filled from dp[0] = 0 upward. Both compute each of the amount subproblems once, giving O(amount × number of coins) — polynomial where the naive recursion was exponential. The two styles trade off: top-down is closer to the recurrence and only computes reachable subproblems; bottom-up avoids recursion overhead and makes the order explicit. Same answers, same complexity, and the transformation from naive is purely the addition of memory.

Complexity: how it scales

The coin-change DP is O(amount × number of coins): each of the amount subproblems is solved once, and each tries every coin. Space is O(amount) for the table. The naive recursion, by contrast, is exponential in the amount, because it re-explores the same subamounts along every path. The face-off counts the work directly — recursive calls made by the naive version versus units of work done by the DP, as the amount grows:

On a log scale the naive line is a straight climb — exponential growth — while the DP line is nearly flat, growing linearly with the amount. At a target of 20 with three coins, the naive recursion made about 38,000 calls; the DP does 60 units of work — a 640-fold difference at a tiny amount, and the gap explodes as the amount grows (at amount 40 the naive version would make billions of calls while the DP does 120). This is the signature of dynamic programming: it doesn't just speed things up by a constant factor, it changes the complexity class, from exponential to polynomial, by refusing to compute the same thing twice. And it solves what greedy couldn't — on these random coin systems, greedy returned a worse answer than the DP on about 13% of instances, silently, because greedy has no way to reconsider a locally-good choice that turns out to be globally wrong.

What it's good at, what it isn't

Dynamic programming is the right tool when a problem has optimal substructure and overlapping subproblems — which describes an enormous range of optimization and counting problems. Shortest paths with choices (Bellman-Ford, Floyd-Warshall are DP), sequence problems (edit distance, longest common subsequence, sequence alignment in bioinformatics — the next two chapters), the knapsack family, matrix-chain multiplication, optimal binary search trees, parsing (the CYK algorithm), text justification, and countless scheduling and resource problems. It's also the computational core of reinforcement learning (value iteration solves the Bellman equation) and speech/handwriting recognition (the Viterbi algorithm is DP on a hidden Markov model). Whenever greedy fails because a locally-best choice can be globally wrong, and the subproblems overlap, DP is usually the answer.

Where it's the wrong tool is problems without overlapping subproblems (use divide and conquer — DP's table would just store single-use values) or without optimal substructure (DP's recurrence would be invalid, as for longest simple paths or many graph problems). It can also be defeated by the number of distinct subproblems: if the state space is exponential — as in the traveling salesman, where a DP state is a subset of cities, giving O(2ⁿ · n) — DP helps (it beats the O(n!) brute force) but is still exponential, only feasible for small n. And DP's tables can consume significant memory; when the state space is huge but each state depends on few others, that's a real constraint, sometimes eased by the rolling-array trick. DP is powerful but not magic — it requires the two properties, and its cost is the size of the state space.

The data, or the inputs

The face-off counts recursive calls made by the naive coin-change recursion against the fixed O(amount × coins) work of the DP, for coins {1,3,4} as the target amount grows — exponential against linear. Correctness is checked by cross-validating all four implementations — naive, top-down memo, bottom-up table, and functools.lru_cache — against each other on hundreds of random coin systems, confirming the reconstructed coin set sums to the amount, and counting how often the greedy algorithm returns a worse answer (76 of 600 instances). The animation fills the bottom-up table for coins {1,3,4} up to amount 11, showing each dp[a] computed from the smaller entries it depends on.

Build it, one function at a time

The naive recursion — correct, but exponential from recomputing overlapping subproblems:

def coin_change_naive(coins, amount, calls=None):
    """The direct recursion: the fewest coins for `amount` is 1 plus the best over all coins c of
    the fewest coins for `amount - c`. Correct, but with NO memory it re-solves the same
    subamounts exponentially many times — the overlapping-subproblems disaster. `calls` counts
    invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    best = float("inf")
    for c in coins:
        best = min(best, 1 + coin_change_naive(coins, amount - c, calls))
    return best

Top-down dynamic programming — the same recursion with a memo cache:

def coin_change_topdown(coins, amount):
    """Top-down dynamic programming (memoization): the same recursion, but cache each subamount's
    answer the first time it's computed and return the cache on every reuse. Each of the `amount`
    distinct subproblems is solved once, so O(amount · len(coins)). Returns the fewest coins, or
    inf if the amount can't be made."""
    memo = {0: 0}

    def best(a):
        if a < 0:
            return float("inf")
        if a in memo:                            # already solved this subproblem — reuse it
            return memo[a]
        memo[a] = min((1 + best(a - c) for c in coins), default=float("inf"))
        return memo[a]

    return best(amount)

Bottom-up dynamic programming — fill a table from the smallest amounts, and reconstruct the coins:

def coin_change_bottomup(coins, amount):
    """Bottom-up dynamic programming (tabulation): fill a table dp[0..amount] from small amounts
    up, each entry using only already-computed smaller ones — dp[a] = 1 + min over coins of
    dp[a-c]. No recursion, no stack. Also track the coin chosen at each amount so the actual coin
    set can be reconstructed. Returns (fewest_coins, coins_used)."""
    dp = [0] + [float("inf")] * amount           # dp[a] = fewest coins to make a
    pick = [None] * (amount + 1)                 # which coin was used to reach dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0 and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c
    if dp[amount] == float("inf"):
        return float("inf"), []
    used, a = [], amount                         # walk the choices back to list the coins
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[amount], sorted(used, reverse=True)

Watch it work

Here's the bottom-up table for coins {1,3,4}, filling from amount 0 up to 11. Each cell dp[a] holds the fewest coins to make amount a; it starts at ∞ (dark) and becomes a number (grey) once computed. Watch a cell being filled (orange): to compute dp[a], the algorithm looks at the already-computed cells dp[a-1], dp[a-3], and dp[a-4] (highlighted blue) — the amounts reachable by removing one coin — and takes the smallest, plus one. Because every cell it consults is to its left and already done, the table fills left to right with no recursion and no recomputation. By amount 11 the answer is 3 coins (4+4+3). And notice dp[6] = 2 (3+3) — exactly where greedy went wrong last chapter with 4+1+1; the table considered all first-coin choices, so it found the pairing greedy's largest-first rule missed:

The complete code

The from-scratch tab is all three versions — naive, top-down, bottom-up — so you can see the transformation is purely the addition of memory; the library tab is the greedy contrast (wrong 13% of the time) and the functools.lru_cache version that gets top-down DP with a one-line decorator. Flip between them.

"""Dynamic programming — solve a problem whose subproblems OVERLAP by computing each subproblem
once and remembering the answer. Divide and conquer assumed independent subproblems; when they
overlap instead — the same smaller instance needed over and over — plain recursion re-solves it
exponentially many times. Dynamic programming fixes that with one idea: a table. Compute each
distinct subproblem a single time, store it, and look it up on every reuse.

The example is minimum-coin change: given coin denominations and a target amount, use the FEWEST
coins to make it. This is exactly the problem greedy couldn't solve — for coins {1,3,4}, greedy
makes 6 as 4+1+1 (three coins) while the optimum is 3+3 (two). It has the two properties every DP
needs: OPTIMAL SUBSTRUCTURE (the best way to make n uses the best way to make some smaller amount)
and OVERLAPPING SUBPROBLEMS (making 6 and making 5 both need the answer for making 2). This chapter
shows the same recurrence three ways — naive (exponential), top-down memoized, and bottom-up
tabulated — the classic progression that turns an exponential algorithm into a linear one.
"""


# region: naive
def coin_change_naive(coins, amount, calls=None):
    """The direct recursion: the fewest coins for `amount` is 1 plus the best over all coins c of
    the fewest coins for `amount - c`. Correct, but with NO memory it re-solves the same
    subamounts exponentially many times — the overlapping-subproblems disaster. `calls` counts
    invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    best = float("inf")
    for c in coins:
        best = min(best, 1 + coin_change_naive(coins, amount - c, calls))
    return best
# endregion


# region: topdown
def coin_change_topdown(coins, amount):
    """Top-down dynamic programming (memoization): the same recursion, but cache each subamount's
    answer the first time it's computed and return the cache on every reuse. Each of the `amount`
    distinct subproblems is solved once, so O(amount · len(coins)). Returns the fewest coins, or
    inf if the amount can't be made."""
    memo = {0: 0}

    def best(a):
        if a < 0:
            return float("inf")
        if a in memo:                            # already solved this subproblem — reuse it
            return memo[a]
        memo[a] = min((1 + best(a - c) for c in coins), default=float("inf"))
        return memo[a]

    return best(amount)
# endregion


# region: bottomup
def coin_change_bottomup(coins, amount):
    """Bottom-up dynamic programming (tabulation): fill a table dp[0..amount] from small amounts
    up, each entry using only already-computed smaller ones — dp[a] = 1 + min over coins of
    dp[a-c]. No recursion, no stack. Also track the coin chosen at each amount so the actual coin
    set can be reconstructed. Returns (fewest_coins, coins_used)."""
    dp = [0] + [float("inf")] * amount           # dp[a] = fewest coins to make a
    pick = [None] * (amount + 1)                 # which coin was used to reach dp[a]
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0 and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                pick[a] = c
    if dp[amount] == float("inf"):
        return float("inf"), []
    used, a = [], amount                         # walk the choices back to list the coins
    while a > 0:
        used.append(pick[a])
        a -= pick[a]
    return dp[amount], sorted(used, reverse=True)
# endregion

"""The contrast and a cross-check. Two references here:

- `greedy_change` is the greedy algorithm from the previous chapter — take the largest coin that
  fits, repeat. It's fast and optimal for 'canonical' coin systems (like real currency) but WRONG
  in general, and it's the contrast that motivates dynamic programming. The trace generator counts
  how often it returns a suboptimal (or impossible) answer that DP gets right.
- Python's `functools.lru_cache` turns the naive recursion into top-down DP automatically by
  memoizing calls — the standard-library way to get memoization for free, and a cross-check that
  our hand-written memo agrees.

    from functools import lru_cache
    @lru_cache(maxsize=None)
    def best(a): ...
"""
from functools import lru_cache


# region: greedy
def greedy_change(coins, amount):
    """Largest-coin-first greedy: repeatedly take the biggest coin that fits. Optimal for currency-
    like systems, but for {1,3,4} making 6 it takes 4+1+1 (3 coins) where the optimum is 3+3 (2).
    Returns the coin count, or inf if it gets stuck (greedy can even fail to make an amount that
    IS makeable). The cautionary contrast to DP."""
    count, a = 0, amount
    for c in sorted(coins, reverse=True):
        while a >= c:
            a -= c
            count += 1
    return count if a == 0 else float("inf")
# endregion


# region: lru
def coin_change_lru(coins, amount):
    """Top-down DP via functools.lru_cache — memoization the standard-library way. A cross-check
    that our hand-rolled memo table matches Python's automatic one."""
    coins = tuple(coins)

    @lru_cache(maxsize=None)
    def best(a):
        if a == 0:
            return 0
        if a < 0:
            return float("inf")
        return min((1 + best(a - c) for c in coins), default=float("inf"))

    return best(amount)
# endregion

Scratch vs library

The three from-scratch versions tell the whole story: naive, top-down, and bottom-up produce identical answers, and the only difference between the exponential one and the polynomial ones is memory. That's the paradigm's essence, and it reframes dynamic programming from an intimidating technique into a simple discipline — write the recurrence (that's the hard, creative part: defining the state and the transition), then add a cache. Python's functools.lru_cache makes the point almost too well: decorate the naive recursion and it becomes efficient top-down DP with no other change. The genuinely difficult part of DP is never the memoization; it's recognizing that a problem has optimal substructure and finding the right state — the same insight that makes greedy provably correct or reveals that it isn't. The coin-change continuity from last chapter is deliberate: greedy failed here because a locally-best choice can be globally wrong, and DP succeeds precisely by considering all choices for each subproblem while paying only once per subproblem. When greedy's exchange argument won't go through, this is the tool.

Where you'll actually meet it

Dynamic programming runs across computing. Shortest-path routing (Bellman-Ford, Floyd-Warshall, and the Viterbi algorithm in error-correcting codes and speech recognition) is DP. Bioinformatics aligns DNA and protein sequences with it (Needleman-Wunsch, Smith-Waterman — next chapters' edit distance generalized). Version control and diff compute longest common subsequences with it. Compilers use it for optimal instruction selection and parsing (the CYK algorithm). Reinforcement learning's value and policy iteration solve Bellman's equation directly. Natural-language processing, spell-checkers (edit distance), text layout (TeX's line-breaking is DP), financial option pricing (binomial trees), and resource scheduling all lean on it. It's also one of the most common interview topics, precisely because recognizing the DP structure in a disguised problem is the core skill. Wherever an optimization problem decomposes into overlapping subproblems, dynamic programming is likely underneath.

Takeaways

Dynamic programming solves problems with optimal substructure and overlapping subproblems by computing each subproblem once and remembering it — top-down via a memo cache, or bottom-up by filling a table from the smallest subproblems. It turns exponential naive recursion into polynomial time (641× less work at amount 20, and the gap only grows), and it solves the optimization problems greedy can't, because it considers every choice for each subproblem rather than committing to a locally-best one. The transformation from naive recursion is purely the addition of memory; the real skill is defining the state and recognizing the substructure.

The next two chapters put dynamic programming to work on its most famous problems. The knapsack family (next) — choosing a maximum-value subset under a weight limit — is the DP that greedy provably can't crack, and it introduces the important distinction between problems whose DP is polynomial and those (like 0/1 knapsack) that are only pseudo-polynomial. Then edit distance and longest common subsequence bring DP to sequences, the two-dimensional tables behind spell-checkers, diff, and DNA alignment.