Dynamic Programming Intro

DP is the pattern with the scariest reputation and the most mundane reality: it is the recursion you already wrote in module 10, plus a notebook so you never solve the same subproblem twice. Interviewers love it because it separates people who memorized solutions from people who can derive them. This module’s only goal is to get you deriving.

The Goal

By the end of this module you can:

• Explain DP as “recursion + a cache” in one sentence, and name the two requirements a problem must meet
• Convert an exponential recursive function into an O(n) one by adding memoization — and say exactly why the speedup happens
• Implement tabulation for climbing stairs in Java, then squeeze the table down to two variables
• Apply the 4-step DP recipe (state → recurrence → base cases → fill order) to a problem you have never seen
• Recognize DP wording in 30 seconds — and spot when greedy from module 09 is secretly enough
• Solve the coin change problem that greedy got wrong, with a table that gets it right

The Lesson

DP is not a new technique

Here is the secret the scary name hides: you already know 90% of DP. In module 10 you wrote recursive functions that break a problem into smaller versions of itself. DP adds exactly one idea on top:

If your recursion solves the same subproblem more than once, write the answer down the first time and look it up after that.

That’s it. Recursion plus a notebook. The notebook is a HashMap or an array. Everything else — top-down, bottom-up, state, recurrence — is vocabulary around that one idea.

Watch the waste: fib without a notebook

The classic demonstration. Fibonacci, written exactly the way module 10 taught you:

static long fibNaive(int n) {
    if (n <= 1) return n;                          // base cases
    return fibNaive(n - 1) + fibNaive(n - 2);      // recursive case
}

Correct. Clean. And catastrophically slow. Draw the call tree for fibNaive(5):

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]
    E --> J["fib(1)"]
    E --> K["fib(0)"]

Look at the duplicates. fib(3) is computed twice. fib(2) three times. Every level of the tree roughly doubles the work, so the total is O(2^n) — fibNaive(50) makes over a trillion calls for a question with 51 distinct answers (fib(0) through fib(50)).

A trillion calls to produce 51 facts. That gap — exponential calls, linear distinct subproblems — is the entire reason DP exists.

Memoization: top-down, the recursion you already wrote + a cache

Add the notebook. Same function, three new lines:

static long fibMemo(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];              // already solved? look it up
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];                                // solve once, write it down
}
// call it: fibMemo(50, new long[51])

Now each fib(k) is computed exactly once and every repeat is an O(1) array read. O(2^n) becomes O(n). Not “a bit faster” — fib(50) drops from minutes to microseconds. The cache is an array here because the subproblem is identified by one small integer; when the state is messier (a pair of indexes, a string position plus a budget), use a HashMap with a composite key.

This style is called memoization, or top-down DP: you start from the big question and recurse down, caching as you return. It is the easiest DP to write because step one is literally “write the module 10 recursion.”

The two requirements — when does the notebook trick apply?

DP only works when the problem has both of these properties. Plain words, with a test for each:

Fib passes both trivially. Most counting and min/max-over-choices problems pass both. Backtracking problems from module 10 where every state is unique (permutations, N-Queens boards) fail the first test — that’s why those stay backtracking.

Tabulation: bottom-up, fill the table from the base cases

Memoization starts at the top and recurses down. Tabulation flips it: start at the base cases and fill a table upward with a loop. No recursion, no stack overflow risk, and usually a touch faster.

The standard first problem: Climbing Stairs. You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways to reach the top?

Think recursively first: to stand on step i, your last move came from step i-1 (a 1-step) or step i-2 (a 2-step). So:

ways(i) = ways(i - 1) + ways(i - 2)

Same shape as fib. Now build it bottom-up:

static int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;                          // one way to reach step 1
    dp[2] = 2;                          // 1+1 or 2
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // the recurrence, as a loop
    }
    return dp[n];
}

Walk it for n = 6, filling left to right:

Each cell is just the sum of the two cells before it. By the time the loop reaches i, both answers it needs already sit in the table. That ordering — every cell ready before it’s needed — is what “fill order” means.

The space optimization: stare at the loop. dp[i] only ever reads dp[i-1] and dp[i-2]. The rest of the table is dead weight. So keep just two variables:

static int climbStairsO1(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;           // dp[i-2], dp[i-1]
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;                       // O(n) time, O(1) space
}

This “shrink the table to the last few cells” move works whenever the recurrence only looks back a fixed distance. Interviewers ask for it as the follow-up almost every time.

The 4-step DP recipe

Every DP solution you will ever write follows this:

flowchart LR
    A["1 Define the state in English"] --> B["2 Write the recurrence"]
    B --> C["3 Set base cases"]
    C --> D["4 Pick the fill order"]

1. Define the state — in English, in one sentence. dp[i] = “the number of ways to reach step i”. If you cannot say what a cell means in plain words, stop — everything after this step is guessing. This is where DP problems are actually won.
2. Write the recurrence. How does dp[i] follow from smaller states? This is always a question about the last choice made: “the final move was X or Y, so combine those cases.”
3. Set base cases. The smallest inputs where the answer is known without any choices.
4. Pick the fill order. For tabulation: loop so dependencies are filled before they’re read (usually left to right). For memoization: skip this step — recursion finds the order for you.

The recipe on a real problem: House Robber

You’re a robber on a street of houses; money[i] is the cash in house i. Rob any houses you like, but never two adjacent ones (alarms). Maximize the loot.

Run the recipe:

1. State: dp[i] = “the maximum loot possible considering only houses 0 through i.”

2. Recurrence: stand at house i. Two choices — take it (then house i-1 is off-limits, so you add money[i] to dp[i-2]) or skip it (your best is whatever dp[i-1] was):

   dp[i] = max(dp[i-1], dp[i-2] + money[i])
   

3. Base cases: dp[0] = money[0]; dp[1] = max(money[0], money[1]).

4. Fill order: left to right. And the recurrence only looks back two cells — so two variables again:

static int rob(int[] money) {
    int prev2 = 0, prev1 = 0;           // best up to i-2, best up to i-1
    for (int cash : money) {
        int curr = Math.max(prev1, prev2 + cash);   // skip vs take
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

For {2, 7, 9, 3, 1}: the table fills 2, 7, 11, 11, 12 — rob houses 0, 2, 4 for 12. The take/skip decision with a no-adjacent constraint is a DP shape you will meet again and again, in different costumes.

When greedy fails, DP is the answer

Back in module 09 you saw greedy break on coin change: a currency with coins {1, 5, 6} and a target of 10. Greedy grabs the biggest coin first — 6, then 1, 1, 1, 1 — five coins. The real answer is 5 + 5 — two coins. Greedy committed to 6 and could never un-commit.

DP doesn’t commit. It tries every coin as the last coin and keeps the best:

1. State: dp[a] = “minimum coins to make amount a.”
2. Recurrence: the last coin used was some c, so dp[a] = min over all coins c of (dp[a - c] + 1).
3. Base case: dp[0] = 0.
4. Fill order: amounts 1 up to the target.

static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    java.util.Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a && dp[a - c] != Integer.MAX_VALUE) {
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

dp[10] checks “last coin was 1, 5, or 6” against dp[9], dp[5], dp[4] — and dp[5] + 1 = 2 wins. The rule of thumb: greedy works when the locally best choice provably never hurts you later; the moment a choice now changes what’s optimal later, you need DP to explore both branches. When in doubt, hunt for one counterexample to greedy. Find one, and it’s DP.

Honest words: this module is the door, not the room

DP mastery takes months. There are 2-D tables, knapsacks, interval DP, DP on strings, DP on trees — and fluency comes only from reps. Don’t measure yourself against that today.

What this module can give you, fully, is two things: the reflex of recognizing “this is DP” from the wording, and the ability to write memoized recursion — module 10 recursion plus a cache — for 1-D problems. That combination already solves the most common interview DP questions. Tabulation fluency, the fancy table shapes, the exotic states: those come with practice, not with reading. Walk through the door; the room takes months and that’s normal.

See It Move

First, the moment this whole module builds to. Play the naive fib(5) tree, then flip the memo toggle ON and watch the duplicate subtrees collapse into cache hits — that collapse IS dynamic programming.

Step through it and notice:

• In naive mode, count how many times fib(2) gets fully expanded — every copy is wasted work
• With memo ON, only the first visit to each value expands; every repeat short-circuits as a cache hit
• The pruned tree has one expansion per distinct value — that is the visual proof of O(2^n) becoming O(n)
• The memo version is the exact same recursion — nothing about the logic changed, only the notebook was added

Now the bottom-up view: climbing stairs as a table filling left to right, no recursion anywhere.

Step through it and notice:

• The first cells are the base cases — written down before any loop logic runs
• Every new cell is computed purely from cells already filled — that is what a valid fill order guarantees
• At any moment, only the last two cells matter for the next one — the space optimization is staring at you

Spot The Pattern

Where It Runs In Real Life

Diff tools and git merge. When git shows you a diff or merges branches, it computes the minimum set of insertions and deletions turning one file into another — the edit distance family of DP. Every git diff you run executes a descendant of the table you built today.

Spell check and autocorrect. Your phone suggesting “minimum” when you typed “minimun” is edit distance again: a DP table scoring how few single-character edits separate your typo from each dictionary word, with the cheapest candidates surfacing as suggestions.

Route planning. Shortest-path engines exploit optimal substructure directly: the best route from Chennai to Delhi through Nagpur must contain the best route from Chennai to Nagpur. Algorithms like Bellman-Ford and Floyd-Warshall are DP over distances, recomputing nothing.

Text wrapping in word processors. Deciding where to break lines so a paragraph looks even is a minimize-total-ugliness DP — greedy line breaking creates rivers of whitespace, which is why high-quality typesetters compute optimal breaks over the whole paragraph instead.

Resource allocation in cloud schedulers. Packing jobs onto machines with CPU and memory limits to maximize value is the knapsack problem — take/skip with a capacity constraint, House Robber’s bigger sibling. Schedulers and capacity planners run knapsack-style DP (and approximations of it) constantly.

Build This

You’re building DpLab.java — naive fib, memoized fib, and the climbing stairs table — and timing the difference with your own eyes.

1. Create a folder dplab, and inside it a file DpLab.java:

public class DpLab {

    static long naiveCalls = 0;

    public static void main(String[] args) {
        int n = 45;

        long start = System.currentTimeMillis();
        long slow = fibNaive(n);
        long naiveMs = System.currentTimeMillis() - start;
        System.out.println("naive  fib(" + n + ") = " + slow
                + "  calls: " + naiveCalls + "  time: " + naiveMs + " ms");

        start = System.nanoTime();
        long fast = fibMemo(n, new long[n + 1]);
        long memoUs = (System.nanoTime() - start) / 1000;
        System.out.println("memo   fib(" + n + ") = " + fast
                + "  time: " + memoUs + " microseconds");

        System.out.println("stairs(10) ways = " + climbStairs(10));
    }

    static long fibNaive(int n) {
        naiveCalls++;
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    static long fibMemo(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    static int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
            System.out.println("dp[" + i + "] = " + dp[i]);
        }
        return dp[n];
    }
}

2. Compile and run:

javac DpLab.java
java DpLab

Read the output slowly. The naive call counter will show billions of calls and several seconds; the memoized version answers the identical question in microseconds. Same recursion. One notebook.

3. Break it — kill the cache. Comment out the if (memo[n] != 0) return memo[n]; line, recompile, run. The “memo” version is now just naive fib with extra steps. Put the line back. The lesson: the lookup-before-recursing line IS the entire optimization.

4. Break it — kill a base case. Change if (n <= 1) return n; in fibNaive to if (n == 1) return n; and run. You get a StackOverflowError — fibNaive(0) recurses to -1, -2, forever. Read the repeating stack trace like module 10 taught you, then fix it. Base cases are where DP tables and recursions are anchored; lose one and everything falls.

5. Extend it — space-optimize. Rewrite climbStairs with two variables instead of the array (the climbStairsO1 version from the lesson). Verify stairs(10) still prints 89.

6. Extend it — House Robber. Add the rob method from the lesson and call it with {2, 7, 9, 3, 1}. Confirm you get 12, and say out loud which houses that corresponds to before checking by hand.

Problems To Solve

The rule: solve until you can write the template from memory; if stuck 25 minutes, read the approach, close it, re-solve from scratch. For DP specifically, always write the state definition in English before touching code — if the sentence is mushy, the code will be too.

Check Yourself

1. DP in one sentence — what is it, in terms of module 10?
2. Name the two requirements a problem must meet for DP, and give the quick test for each.
3. Why is naive fib O(2^n) but memoized fib O(n)? What exactly changed?
4. Memoization vs tabulation — which direction does each work in, and which one is “the recursion you already wrote”?
5. What are the four steps of the DP recipe, in order?
6. Write the House Robber recurrence and say what each term means in English.
7. Coins {1, 5, 6}, amount 10: what does greedy answer, what is the right answer, and what does DP do differently?
8. In climbing stairs, why can the whole dp table be replaced by two variables?

Explain it out loud: Face the empty chair and explain why fibNaive(50) takes minutes but fibMemo(50) is instant — draw the call tree in the air, show where the duplicates are, and describe what the cache does to them. Then state the 4-step recipe and run it on House Robber from memory. Stall anywhere, re-read that section.

Still Unclear?

Copy-paste any of these into Claude — they’re built to deepen understanding, not to do the work for you:

I understand fib with memoization, but I freeze on step 1 of the DP recipe:
defining the state. Give me five one-line problem statements, and for each,
make me propose a state definition in plain English first. Only after I
answer, tell me if my state is sufficient, and why or why not. No code.

Take the coin change problem with coins {1, 5, 6} and amount 10. I know
greedy fails here. Walk me through the dp array index by index, asking ME
to predict each cell before you reveal it. If I get one wrong, stop and
make me explain the recurrence again instead of just correcting me.

Quiz me on the boundary between greedy and DP. Give me 6 short problems,
mixed: some where greedy is provably safe, some where it fails. For each,
I will answer greedy or DP and justify it; you tell me if my justification
would survive a counterexample. Keep score.

Why AI Can’t Do This For You

AI will write a flawless memoized solution to any named DP problem in seconds — Climbing Stairs, House Robber, Coin Change, all of them are in its training data a thousand times over. What it cannot do is sit in your interview when the problem is worded as “a delivery rider chooses orders, but accepting one blocks the next pickup slot” and recognize, in 30 seconds, that this is take/skip DP wearing a costume. That recognition — wording to pattern, pattern to state definition — happens in your head or not at all.

The same gap shows up at work. A vague ticket says the pricing engine is slow, and the cause turns out to be a recursive discount calculation re-solving the same sub-cases thousands of times per request. Nobody hands you a LeetCode title; the person who has felt the exponential-to-linear collapse — who watched the tree prune itself in this module — is the one who spots the missing cache. A prompt can write the fix. It can’t notice the problem.

Module done? Add it to today’s tracker