Dynamic Programming Introduction

Dynamic programming (DP) is a technique for solving problems by breaking them into smaller, overlapping subproblems, solving each subproblem exactly once, and reusing the stored result instead of recomputing it. Done right, DP turns algorithms that would take exponential time — because the same smaller problem gets solved over and over — into algorithms that run in polynomial time. DP isn’t a single algorithm; it’s a strategy you reach for whenever a problem has two properties: optimal substructure (the best answer to the whole problem can be built from the best answers to its pieces) and overlapping subproblems (those pieces repeat many times). This lesson builds the core toolkit — recognizing when DP applies, memoization (top-down), tabulation (bottom-up), and how to reason about state and recurrence — using the Fibonacci sequence and a staircase-climbing problem as running examples.

Overview: What Makes a Problem “Dynamic Programming”

Consider computing the 5th Fibonacci number with the textbook recursive definition fib(n) = fib(n - 1) + fib(n - 2). To compute fib(5), you need fib(4) and fib(3). To compute fib(4), you need fib(3) and fib(2) — notice fib(3) is now needed twice. Keep expanding and fib(2) gets computed three times, fib(1) five times, and so on. The recursion tree branches exponentially, but it’s full of duplicate work: the same subproblem is solved again and again from scratch. That duplication is the signature of overlapping subproblems. Fibonacci also has optimal substructure: the answer for n is built directly from the answers for smaller n — there’s no need to reconsider the whole problem once you know fib(n - 1) and fib(n - 2).

Once you spot both properties, DP gives you two equivalent ways to eliminate the duplicate work:

Top-down (memoization): keep the natural recursive structure, but cache the result of every subproblem the first time it’s computed (usually in a dict or array). The next time the same subproblem is requested, return the cached answer instead of recomputing. This is usually the easiest transformation to make from a brute-force recursive solution — you write the recursion first, then add a cache.

Bottom-up (tabulation): flip the direction. Start from the base case(s) and iteratively fill in a table (usually a list) of subproblem answers, in an order that guarantees every value a step depends on has already been computed. This avoids function-call overhead and Python’s recursion depth limit entirely, and often lets you shrink the table down to just the last few values you still need.

Whichever direction you pick, the real work of solving a DP problem happens before you write any code: (1) define the state in words — what does dp[i] (or dp[i][j]) actually represent? (2) write the recurrence — how does a state’s answer relate to smaller states’ answers? (3) identify the base case(s) — the smallest states you can answer directly, with no further recursion. Get those three things right and the code is usually short.

Time and Space Complexity

The whole point of DP is the complexity difference between “recompute everything” and “compute each subproblem once.” For a problem with n distinct subproblems, each costing O(1) to combine once its dependencies are known:

Approach Time Space Why
Naive recursion (no caching) O(2^n) O(n) (call stack depth) Every call branches into two more calls; the recursion tree has roughly 2^n nodes because subproblems are recomputed instead of reused.
Top-down memoization O(n) O(n) (memo table + call stack) Each of the n distinct subproblems is computed exactly once and then served from the cache; O(1) work to combine two already-known results.
Bottom-up tabulation O(n) O(n) table, or O(1) if only a fixed number of previous entries are needed Same one-computation-per-subproblem guarantee as memoization, without recursion overhead; space can often be reduced by keeping only the last k table entries.

This is the general pattern across nearly every DP problem: naive recursion is exponential in the number of independent choices, while memoization or tabulation is polynomial in the number of distinct states — often O(n) or O(n·m) for two-dimensional state spaces like grid paths or string-alignment problems. Always state your complexity in terms of the number of distinct states, not just “n”: a DP over a string of length n and a target sum k typically costs O(n·k), not O(n).

Examples

Example 1: Naive Recursive Fibonacci (and why it’s slow)

Start with the brute-force recursive translation of the definition, with no caching at all. It’s correct, but it recomputes the same subproblems repeatedly:

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


def main() -> None:
    result = fib_naive(10)
    print(f"fib(10) = {result}")


if __name__ == "__main__":
    main()

Output:

fib(10) = 55

Tracing fib_naive(10) by hand takes a while precisely because of the duplication described above — but the point of this example is to see it run correctly on a small input before looking at why it doesn’t scale. fib_naive(0) and fib_naive(1) return immediately since n <= 1. For n = 10, the calls fan out into two branches at every level, and by the time the recursion bottoms out, fib_naive(3) alone has been recomputed from scratch several times across different branches of the tree. The result is still correct — 55 — but the number of function calls roughly doubles for every unit increase in n, exactly matching the O(2^n) bound from the table above. Try changing 10 to 35 and it noticeably slows down; that’s the exponential blowup made visible.

Example 2: Top-Down Memoization

Add a cache and the exact same recursive shape becomes fast:

def fib_memo(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]


def main() -> None:
    print(f"fib(10) = {fib_memo(10)}")
    print(f"fib(30) = {fib_memo(30)}")


if __name__ == "__main__":
    main()

Output:

fib(10) = 55
fib(30) = 832040

fib_memo starts a fresh, empty memo dict for each top-level call (because memo defaults to None and is only created inside the function — more on why that matters in Common Mistakes below). Computing fib_memo(30) still recurses down the same way fib_naive would, but the first time fib(3) is computed its result is stored in memo[3]; every later call that needs fib(3) reads it straight out of the dict in O(1) instead of re-expanding the recursion. That’s why fib(30) — which would take well over a billion recursive calls the naive way — returns instantly here.

Example 3: Bottom-Up Tabulation (Staircase Climbing)

Now a more realistic, interview-style problem: given a staircase of n steps, and the ability to climb either 1 or 2 steps at a time, how many distinct sequences of moves reach the top? This is solved bottom-up, without recursion at all:

def count_ways(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for step in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1


def main() -> None:
    for n in range(1, 6):
        print(f"n={n}: {count_ways(n)} ways")


if __name__ == "__main__":
    main()

Output:

n=1: 1 ways
n=2: 2 ways
n=3: 3 ways
n=4: 5 ways
n=5: 8 ways

count_ways(n) answers “how many distinct sequences of 1-step and 2-step moves reach step n?” using bottom-up tabulation, without ever building an explicit array — it only ever needs the previous two answers to compute the next one, so prev2 and prev1 play the role of a rolling table. Starting from the base case that there’s exactly one way to be standing at step 0 or step 1, each loop iteration computes the next value as the sum of the previous two — exactly the Fibonacci recurrence, because this problem is Fibonacci in disguise. The output matches what you’d get by listing paths by hand: 1, 2, 3, 5, 8 ways for n = 1 through 5.

How It Works Step by Step

Let’s make the bottom-up computation from Example 3 fully explicit by writing out every table entry it would produce if it stored a full array dp, where dp[step] is the number of ways to reach that step, for n = 5:

step dp[step] how it was computed
0 1 base case — one way to be standing at the ground (no moves taken)
1 1 base case — the only way to reach step 1 is a single 1-step move
2 2 dp[1] + dp[0] = 1 + 1
3 3 dp[2] + dp[1] = 2 + 1
4 5 dp[3] + dp[2] = 3 + 2
5 8 dp[4] + dp[3] = 5 + 3

Each entry only reads values that were already finalized earlier in the table — that’s the ordering guarantee bottom-up tabulation depends on: by the time dp[step] is computed, both dp[step - 1] and dp[step - 2] already hold their final answers. This is also exactly the invariant that top-down memoization enforces implicitly through recursion: a memoized call only returns once both of its recursive dependencies have returned.

Common Mistakes

Mistake 1: Mutable Default Arguments for a Memo Cache

It’s tempting to write the memo dictionary directly as a default argument, since it looks like a convenient one-line cache:

def fib_memo_buggy(n: int, memo: dict = {}) -> int:
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo_buggy(n - 1, memo) + fib_memo_buggy(n - 2, memo)
    return memo[n]

This runs, and even looks like it works — but Python evaluates default argument values exactly once, when the function is defined, not on every call. Because a dict is mutable, every call to fib_memo_buggy that doesn’t explicitly pass a memo shares the exact same dictionary object for the entire lifetime of the program. For a pure, side-effect-free recurrence like Fibonacci this can accidentally look harmless (the cached values happen to always be correct), but it’s a landmine the moment the function’s behavior can legitimately differ between calls — for example if a later version adds a parameter that changes the recurrence, or the same function is reused across a test suite where each test expects a clean cache. The fix is the standard one for any mutable default: default to None and create a fresh dict inside the function body.

def fib_memo_fixed(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo_fixed(n - 1, memo) + fib_memo_fixed(n - 2, memo)
    return memo[n]


def main() -> None:
    print(f"fib(10) = {fib_memo_fixed(10)}")
    print(f"fib(10) again = {fib_memo_fixed(10)}")


if __name__ == "__main__":
    main()

Output:

fib(10) = 55
fib(10) again = 55

Now every top-level call gets its own memo, and results are still cached correctly within a single call’s recursion.

Mistake 2: Off-by-One Errors in Table Size and Loop Bounds

The second most common DP bug (after the recursion issue above) is sizing the table wrong. If dp[i] needs to represent an answer for every i from 0 up to and including n, the table needs n + 1 slots, not n:

def count_ways_buggy(n: int) -> int:
    dp = [0] * n  # BUG: indices 0..n need n + 1 slots
    dp[0] = 1
    dp[1] = 1
    for step in range(2, n + 1):
        dp[step] = dp[step - 1] + dp[step - 2]
    return dp[n]

dp = [0] * n allocates only n slots, with valid indices 0 through n - 1. The very next line, dp[1] = 1, already raises an IndexError for n = 1 (a list of length 1 only has index 0), and the final dp[n] is always out of range regardless of n. The fix is to allocate one extra slot so index n is valid:

def count_ways_fixed(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for step in range(2, n + 1):
        dp[step] = dp[step - 1] + dp[step - 2]
    return dp[n]


def main() -> None:
    print(f"n=5: {count_ways_fixed(5)} ways")


if __name__ == "__main__":
    main()

Output:

n=5: 8 ways

As a general rule: if a subproblem is naturally indexed by “the answer through position i” for i in [0, n], allocate the table with size n + 1 and double-check the very first and very last iterations by hand — off-by-one mistakes hide exactly at those boundaries.

Best Practices

  • Before coding, write the state definition in one sentence (“dp[i] = the maximum … using the first i items”) — if you can’t state it in one sentence, the state probably isn’t fully defined yet.
  • Derive the brute-force recursive solution first, confirm it’s correct on a small example, then add memoization — it’s easier to get the recurrence right without also juggling loop order at the same time.
  • Reach for functools.lru_cache as a quick, built-in memoization decorator when the state is a small number of hashable arguments; write the cache by hand when it needs custom handling or you want to teach the caching explicitly.
  • Prefer bottom-up tabulation over top-down recursion when n can be large — it avoids Python’s default recursion limit (around 1000) and function-call overhead entirely.
  • Look for a space optimization after correctness: if dp[i] only ever depends on the previous one or two entries, you rarely need the whole table — a couple of rolling variables is often enough, as in Example 3.
  • Reach for DP specifically when a problem asks for an optimal value (min, max, or count) over choices with repeating substructure; if subproblems don’t overlap, plain recursion or divide-and-conquer (like merge sort) is simpler and equally efficient.
  • Trace your recurrence on the smallest 2-3 inputs by hand before trusting the code — base cases are where DP bugs concentrate.

Practice Exercises

  1. Tribonacci numbers. The Tribonacci sequence extends Fibonacci to three terms: T(0) = 0, T(1) = 1, T(2) = 1, and T(n) = T(n - 1) + T(n - 2) + T(n - 3) for n >= 3. Write a memoized function tribonacci(n) and print tribonacci(10). Hint: you need three base cases instead of two, and watch out for the mutable-default-argument mistake from this lesson. Expected output: 149.
  2. House Robber. Given house values [2, 7, 9, 3, 1], you may rob any subset of houses but can never rob two adjacent houses. Find the maximum total value you can rob. Define dp[i] as the best result using only the first i houses, and work out the recurrence between dp[i], dp[i - 1], and dp[i - 2]. Expected output: 12.
  3. Minimum coins. Given coin denominations [1, 3, 4] and a target amount of 6, find the minimum number of coins needed to make exactly that amount, assuming an unlimited supply of each coin. Build a bottom-up table where dp[amount] holds the fewest coins needed for that amount, initialized to a large “infinity” sentinel except dp[0] = 0. Expected output: 2.

Summary

  • Dynamic programming applies when a problem has optimal substructure (answers build from smaller answers) and overlapping subproblems (those smaller answers repeat).
  • Top-down memoization caches recursive calls; bottom-up tabulation iteratively fills a table from base cases upward — both eliminate redundant recomputation.
  • Naive recursion without caching costs O(2^n) time on problems like Fibonacci; memoization and tabulation bring that down to O(n) time, typically O(n) space (sometimes O(1) with a rolling window).
  • Always define the state, recurrence, and base case in words before writing code — most DP bugs come from getting one of those three wrong.
  • Never use a mutable default argument (like memo={}) as a cache — default to None and initialize inside the function.
  • Size tabulation arrays as n + 1 when indices run from 0 to n inclusive, and double-check boundary iterations by hand.