Dynamic Programming — From Recursion to Memoization to Tabulation

Dynamic programming (DP) sounds intimidating, but the idea is simple: if a recursive solution solves the same subproblem again and again, solve each one once and remember the answer. That's it. The skill is in spotting the subproblem.

The motivating example: Fibonacci

def fib(n):               # naive recursion: ~2ⁿ calls
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) computes fib(3) twice and fib(2) three times. For fib(50) that's over 10¹⁰ calls. Remember answers instead:

from functools import lru_cache

@lru_cache(maxsize=None)  # memoization: cache each fib(n) once
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)      # now O(n)

Two styles

Memoization (top-down)	Tabulation (bottom-up)
Recursion + a cache	A loop filling a table from small to large
Easy to write from the recursive idea	No recursion depth limits, often faster
Only computes needed states	Computes all states in order

Both give the same complexity: (number of states) × (work per state).

The 4-step DP recipe

1. State — what does dp[i] (or dp[i][j]) mean, in words?
2. Recurrence — how is dp[i] built from smaller states?
3. Base cases — the smallest states you know directly.
4. Answer & order — which state is the answer, and in what order do you fill the table?

Write step 1 as a sentence before coding. Most DP bugs come from a fuzzy state definition.

1D DP

Climbing Stairs

You can climb 1 or 2 steps. How many ways to reach step n?

1. State: dp[i] = number of ways to reach step i.
2. Recurrence: the last move was a 1-step (from i−1) or a 2-step (from i−2) → dp[i] = dp[i−1] + dp[i−2].
3. Base: dp[0] = 1, dp[1] = 1.
4. Answer: dp[n], fill left to right.

def climb_stairs(n):
    a, b = 1, 1               # dp[i-2], dp[i-1] — only two values needed
    for _ in range(n - 1):
        a, b = b, a + b
    return b

House Robber

Rob houses in a row, but never two adjacent ones. Maximise the money.

• State: dp[i] = best money from the first i houses.
• Recurrence: skip house i → dp[i−1]; rob it → dp[i−2] + nums[i]. Take the max.

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

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

Coin Change (minimum coins)

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount            # dp[a] = fewest coins to make amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)   # last coin used is c
    return dp[amount] if dp[amount] != INF else -1

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

O(amount × coins). Greedy (always take the biggest coin) fails here — e.g. coins [1, 3, 4], amount 6: greedy gives 4+1+1 (3 coins), DP finds 3+3 (2 coins).

Longest Increasing Subsequence

dp[i] = length of the longest increasing subsequence ending at i:

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n²). (There's an O(n log n) version with binary search — a great follow-up to mention.)

2D DP

Longest Common Subsequence

dp[i][j] = LCS length of the first i characters of a and the first j of b.

• If a[i−1] == b[j−1]: dp[i][j] = dp[i−1][j−1] + 1 (use the match).
• Else: dp[i][j] = max(dp[i−1][j], dp[i][j−1]) (drop one character).

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]

Edit Distance has the same table shape with three choices (insert, delete, replace). Unique Paths in a grid: dp[r][c] = dp[r−1][c] + dp[r][c−1].

0/1 Knapsack (Partition Equal Subset Sum)

Can some subset of nums add up to target? For each number, either take it or skip it:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target           # dp[s] = can we make sum s?
    for x in nums:
        for s in range(target, x - 1, -1):   # go DOWN so each number is used once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

Looping s downwards is the key detail that makes it 0/1 (each item once). Looping upwards would allow reuse — that's the unbounded knapsack (Coin Change II).

How to recognise DP

• "Number of ways to…", "minimum/maximum cost/profit…", "longest/shortest subsequence…", "can you reach/make…".
• Choices at each step whose results overlap — the same subproblem appears via different paths.
• Greedy looks tempting but you can find a counter-example.

Common mistakes

1. Jumping to code before defining the state in words.
2. Wrong base case (often dp[0]).
3. Wrong loop order — a state used before it's computed.
4. 0/1 vs unbounded knapsack loop direction.
5. Forgetting that you can usually compress 1D DP to two variables, and 2D to one row.

Key takeaways

• DP = recursion + remembering repeated subproblems.
• Recipe: state → recurrence → base cases → answer & order.
• Complexity = number of states × work per state.
• Start with memoization if tabulation feels hard — it's the same idea.