Friday Night Wiki
TopicsAbout
Buy me a coffee
Algorithms Tutorial

Dynamic Programming: Memoize Your Way to Fast Solutions

This chapter covers memoization, tabulation, and the classic DP problems: knapsack, LCS, edit distance.

What Dynamic Programming Is

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems, solving each subproblem once, and reusing the answers.

Two requirements:

  • Optimal substructure: the optimal solution can be built from optimal solutions to subproblems.
  • Overlapping subproblems: the same subproblems appear multiple times in a naive recursive solution.

When both hold, DP turns exponential recursion into polynomial time by avoiding re-computation.

The Canonical Example: Fibonacci

Naive recursion:

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

fib(40) takes seconds. fib(50) takes minutes. Why? Each call branches into two, giving O(2^n) work. And it recomputes the same values over and over (fib(3) gets called thousands of times).

Memoization (Top-Down)

Cache the results.

from functools import lru_cache

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

Now fib(40) is instant. Each fib(k) is computed once and cached. O(n) time, O(n) space.

functools.lru_cache is Python's one-liner for memoization. In an interview, you can write it by hand:

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

Avoid memo={} as a default argument; mutable defaults leak across calls.

Tabulation (Bottom-Up)

Build the answer iteratively. Same complexity, no recursion overhead, often smaller constants.

def fib(n):
    if n < 2:
        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]

O(n) time, O(n) space.

Space Optimization

You only need the last two values. O(1) space:

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

Common trick: when the DP recurrence only looks back a few steps, you don't need the full table.

Top-Down vs Bottom-Up

Both work. When to pick which:

Top-down (memoization):

  • Code looks like the recursive definition. Easier to write.
  • Only computes subproblems that are actually needed.
  • Slightly more overhead (function call, hash lookup).

Bottom-up (tabulation):

  • Usually faster (no recursion).
  • Computes every subproblem, whether needed or not.
  • Can often save space (keep only the last few rows of the table).

In interviews, write top-down first (it's easier). Convert to bottom-up if asked for space or speed improvements.

Classic DP Problems

Climbing Stairs

You climb 1 or 2 stairs at a time. How many distinct ways to reach stair n?

Recurrence: ways(n) = ways(n-1) + ways(n-2). Same as Fibonacci.

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

Coin Change

Given coin denominations and a target amount, find the minimum number of coins.

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

dp[i] = minimum coins to make amount i. O(amount * len(coins)).

0/1 Knapsack

Given items with weights and values, and a capacity, maximize total value without exceeding capacity. Each item is taken once or not at all.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]    # don't take item
            if weights[i - 1] <= w:
                take = values[i - 1] + dp[i - 1][w - weights[i - 1]]
                dp[i][w] = max(dp[i][w], take)
    return dp[n][capacity]

O(n * capacity) time and space.

The state is (item index, remaining capacity). The answer is whether we take the item or not, and recurse.

Longest Common Subsequence

Given two strings, find the length of the longest subsequence (not necessarily contiguous) present in both.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

dp[i][j] = LCS of a[:i] and b[:j]. O(m * n).

LCS underlies diff, DNA sequence alignment, and plagiarism detection.

Edit Distance (Levenshtein)

Minimum single-character edits (insert, delete, substitute) to turn one string into another.

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],        # delete
                    dp[i][j - 1],        # insert
                    dp[i - 1][j - 1],    # substitute
                )
    return dp[m][n]

Same shape as LCS. Used in spell checkers, fuzzy search, git diff.

How to Spot a DP Problem

Signals that a problem may be DP:

  • "Minimum/maximum/count of ways to do X"
  • The problem has overlapping subproblems (you'd solve the same thing repeatedly in naive recursion)
  • The problem has optimal substructure (optimal answer built from optimal sub-answers)
  • Decision at each step: take or skip, include or exclude, go this way or that

If you can write a brute-force recursion that's exponential, try memoizing it. If the memoized version works, you've solved the DP problem.

Designing a DP Solution

The pipeline:

  1. Define the state. What do the subproblems look like? dp[i] or dp[i][j] or more.
  2. Define the recurrence. How does dp[state] relate to smaller states?
  3. Base cases. What are the trivial answers?
  4. Order of computation. What order lets you fill the table without needing unfilled cells?
  5. Answer. Which cell has the final answer?

Work through these five on paper before writing code. Jumping straight to the loop invites bugs.

When DP Doesn't Fit

Not every recursion benefits from DP.

  • If subproblems don't overlap, memoization doesn't help. Just recurse.
  • If the state space is too large to fit in memory, DP is infeasible; you need approximations.
  • If greedy works, use greedy. It's simpler and often faster. DP is for when greedy isn't provably correct.

Common Pitfalls

Picking the wrong state. A bad state definition leads to a recurrence you can't write. Spend more time on state design.

Forgetting base cases. dp[0] needs a value too. Often 0, 1, or an empty sentinel.

Off-by-one in indices. Especially with 1-indexed DPs over strings of length n. Write a small example and trace.

Memoizing mutable state. @lru_cache needs hashable arguments. Convert lists to tuples before memoizing.

Not optimizing space. Many DPs only need the previous row (or two previous values). If memory matters, roll the table.

Next Steps

Continue to 10-greedy-and-divide-conquer.md for two related problem-solving hammers.