Dynamic Programming

How to recognize DP, the five-step recipe (state, transition, base, order, answer), memoization vs tabulation, and the classic problem families.

Why We Need Dynamic Programming & How to Think About It

Imagine trying to calculate the 5th Fibonacci number: $F(5) = F(4) + F(3)$. To get $F(4)$, you need $F(3) + F(2)$. Notice that $F(3)$ is calculated twice! As $n$ grows, this recursion tree explodes exponentially ($O(2^n)$). If you instead write the answer to $F(3)$ on a sticky note the first time you solve it, you can just look it up next time in $O(1)$. This is Dynamic Programming (DP). It is simply recursion with a memory bank. It trades memory space to avoid re-solving identical subproblems, turning exponential $O(2^n)$ time into linear $O(n)$ time.

The Two Rules of DP (When to Use)

A problem can be solved with DP if it has:

Overlapping Subproblems: The recursion tree visits the same states with the same inputs repeatedly.
Optimal Substructure: The optimal solution to the overall problem can be constructed from optimal solutions to its smaller subproblems.

When it's DP

Two signals together: optimal substructure (the answer is built from answers to subproblems) and overlapping subproblems (the same subproblem recurs). If subproblems don't overlap, it's divide-and-conquer, not DP. Phrasings: "number of ways", "min/max cost/length", "can you reach", "longest …".

The five-step recipe

State — what parameters identify a subproblem? (dp[i], dp[i][j]…)
Transition — how does a state combine smaller states?
Base case(s) — the trivial smallest states.
Order — memoized recursion (top-down) or fill a table (bottom-up).
Answer — which state holds it.

Memoization vs tabulation

Top-down (memoize): write the recursion, cache results. Easiest to derive — start here in an interview.
Bottom-up (tabulate): fill an array in dependency order. No recursion overhead; enables space optimization (keep only the last row/few cells).

Python

# Coin change: fewest coins to make `amount` (unbounded coins).
# Python
def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] < INF else -1
# Time O(amount · coins), Space O(amount)

Java

// Java
public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    java.util.Arrays.fill(dp, max);
    dp[0] = 0;                         // base case: 0 coins for amount 0
    for (int x = 1; x <= amount; x++) {
        for (int c : coins) {
            if (c <= x) {
                dp[x] = Math.min(dp[x], dp[x - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

C++

// C++
#include <vector>
#include <algorithm>

int coinChange(const std::vector<int>& coins, int amount) {
    int max_val = amount + 1;
    std::vector<int> dp(amount + 1, max_val);
    dp[0] = 0;                         // base case: 0 coins for amount 0
    for (int x = 1; x <= amount; x++) {
        for (int c : coins) {
            if (c <= x) {
                dp[x] = std::min(dp[x], dp[x - c] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Watch the table fill

This is the part no amount of reading teaches: watch answers to small questions combine into answers to bigger ones. Four problems on one player — start with Fibonacci (the "hello world" of DP), then coin change (where greedy fails and the table doesn't), then the two 2-D classics.

Dynamic programming — Fibonaccitime O(n)space O(n)

0123456789fib

1/19Goal: the 9th Fibonacci number. Naive recursion recomputes the same values millions of times — instead we'll fill a table once, left to right.

problem

n (2–12)

Classic families (recognize the skeleton)

Family	Examples	State shape
1-D sequence	climbing stairs, house robber, LIS	`dp[i]`
Knapsack	0/1 knapsack, partition equal subset, coin change	`dp[i][capacity]`
Two strings	edit distance, LCS	`dp[i][j]`
Grid	unique paths, min path sum	`dp[r][c]`
Intervals	matrix-chain, burst balloons	`dp[i][j]` over ranges

Derive top-down first, then convert

Get the recurrence right with memoization (it mirrors the brute-force you already described), then convert to bottom-up if you need to optimize space. Trying to write the table directly is where people make indexing errors.

Think it through

The five-step recipe only sticks once you run it yourself. Derive a clean 1-D DP end to end — defining the state in English is 80% of the work.

Think it through: House RobberMedium — LeetCode 1980/5 stages

PROBLEMHouses in a row hold money nums[i]. Robbing two ADJACENT houses triggers the alarm. Maximize the loot. nums = [2,7,9,3,1] → 12 (rob houses 0, 2, 4 → 2+9+1).

1
Restate & edges
“What's the constraint, stripped of the story?”
2
Why DP, not greedy or brute force
“Does grabbing the biggest house first work? What does brute force cost?”
unlocks after the stage above
3
Define the state (the 80%)
“Finish: dp[i] = … and the transition at house i is a choice between what two options?”
unlocks after the stage above
4
Code it (and shrink the space)
“dp[i] only ever reads dp[i-1] and dp[i-2]. So how big does the table need to be?”
unlocks after the stage above
5
Cost & edge check
“Cost, and trace [2,7,9,3,1]?”
unlocks after the stage above

Java

// Java — House Robber (Space Optimized)
public int rob(int[] nums) {
    int prev2 = 0;                     // best loot up to house i-2
    int prev1 = 0;                     // best loot up to house i-1
    for (int money : nums) {
        int robIt = prev2 + money;     // rob i -> must skip i-1
        int skipIt = prev1;            // skip i
        int temp = Math.max(robIt, skipIt);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

C++

// C++ — House Robber (Space Optimized)
#include <vector>
#include <algorithm>

int rob(const std::vector<int>& nums) {
    int prev2 = 0;                     // best loot up to house i-2
    int prev1 = 0;                     // best loot up to house i-1
    for (int money : nums) {
        int robIt = prev2 + money;     // rob i -> must skip i-1
        int skipIt = prev1;            // skip i
        int temp = std::max(robIt, skipIt);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

Check yourself

Check yourself0/4 answered

1. The two signals that together mean 'reach for DP' are:

2. In House Robber, dp[i] = max(dp[i-1], nums[i] + dp[i-2]). What does the 'nums[i] + dp[i-2]' branch mean?

3. Top-down (memoization) vs bottom-up (tabulation):

4. Greedy (largest coin first) gives 4+1+1 for coins {1,3,4}, amount 6. Why does DP get the optimal 3+3?

Practice — climb the ladder

The DP on-ramp: define the state in ENGLISH first ("dp[i] = best answer using the first i items"), then the recurrence, then the base cases.

Practice ladder: Dynamic Programming — Foundations0/9 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up

one-dimensional, one decision per step

Climbing StairsEasy
Fibonacci in costume — your first state definition and recurrence.
Min Cost Climbing StairsEasy
Same shape plus costs — min() enters the recurrence.
House RobberMedium
Take-or-skip — THE template for non-adjacent choice problems.

Core

the four state shapes you must recognize

Maximum SubarrayMedium
Kadane — dp[i] = best ENDING here; extend or restart.
Coin ChangeMedium
Unbounded choices to reach an amount — min-cost reachability.
Longest Increasing SubsequenceMedium
dp[i] anchored at index i, scanning back — O(n²) first, patience-sort later.
Unique PathsMedium
Grid DP — cell = sum of the two cells that can reach it.

Stretch

two sequences = 2D table

Longest Common SubsequenceMedium
The 2D template — match ⇒ diagonal+1, else max(left, up).
Edit DistanceMedium
Same table, three operations — the canonical string-transform DP.