DP — A Masterclass in Thinking

This is long on purpose — it's a course, not a cheat sheet (though the cheat sheets are at the bottom). Read it like this:

Ten parts, front-loaded toward thinking and back-loaded with reference. Jump around with the rail on the right (or the "Sections" button on mobile), but the first read should be in order.

01 · What DP actually is#

Forget "optimal substructure" and "overlapping subproblems" for sixty seconds. Those are true, but they're the diagnosis after the fact, not the feeling. Here is the feeling:

Everything else — states, transitions, tables, memoization — is just bookkeeping in service of that one refusal. Once you believe that DP is "brute force plus a memory," the mystique drops away. You're not inventing a clever formula out of thin air. You're writing the obvious brute-force search, then catching it repeating itself.

The three mental models, ranked by usefulness#

Beginners are taught Model B first (fill this table with this formula) and it's exactly backwards. The table is the destination. Model A — cached recursion — is the road, and it's the road we'll drive the whole way.

Why the "overlapping subproblems" phrase matters after all#

Now we can earn the textbook words. Two properties make DP possible and worth it:

• Optimal substructure — the answer to the big problem can be built from answers to smaller versions of the same problem. (If it can't, caching buys you nothing — there's no smaller answer to reuse.)
• Overlapping subproblems — those smaller versions recur, many times, across the search. (If every subproblem is unique, there's nothing to cache — that's just divide & conquer, e.g. merge sort.)

Hold both in mind as a test you run, not a definition you recite. We'll turn them into concrete questions in Part II.

02 · Why humans struggle with DP#

You are not bad at DP. You are missing a process, and you've been shown products. Editorials present the final recurrence the way a magician presents the rabbit — fully formed, no sleeves shown. Of course it feels like magic; the derivation was edited out. Let's name the specific gaps so we can close them one by one.

03 · Recognizing DP in the wild#

You rarely get told "this is a DP problem." You have to smell it. Here are the smells — the surface features that should make your DP-sense tingle. None is proof; together they're strong evidence.

The recognition signals#

The recognition decision tree#

Run a new problem down this, top to bottom. The first "no" that sends you off DP is your answer.

DP versus its look-alikes#

Half of "recognizing DP" is not confusing it with a neighbor. Here's how each sibling differs, and the one question that separates it from DP.

04 · From blank stare to recurrence#

Here is the pipeline. Every DP solution you will ever write comes out of it. Experienced solvers run it so fast it looks like intuition — but it's just these seven moves, always in this order.

Seeing the repeated work with your own eyes#

Abstract talk about "overlapping subproblems" convinces no one. Let's see it. Below is the actual call tree of naïve recursive Fibonacci, fib(n) = fib(n-1) + fib(n-2). Flip on memoization and watch how much of the tree was pure waste — every greyed, dashed node is a call whose answer we'd already computed.

Naïvely, fib(5) makes 15 calls; with memoization only 6 distinct subproblems are ever computed (one per value 0–5) and the rest are cache hits. That gap is exponential vs linear — O(2ⁿ) → O(n) — from a one-line change. This is why DP feels like a superpower and is actually just "don't recompute."

A full worked derivation: Coin Change (minimum coins)#

Let's run the entire engine on one problem, out loud, mistakes included. Problem: given coins {1, 3, 4} (unlimited of each), make amount 6 using the fewest coins.

Detour: why greedy fails (and how you'd notice)#

Your first instinct is greedy: always grab the biggest coin that fits. Let's try it and watch it break — seeing greedy fail is how you earn the right to reach for DP.

The counterexample is the tell. When a locally-worse choice can win globally, you cannot commit greedily — you must compare futures. Comparing futures is DP.

Step 1 — 2 · Describe the choice, write the recursion#

At any moment I owe some amount. My single choice: which coin do I use next? If I use a coin c ≤ amount, I've spent one coin and now owe amount - c — a smaller instance of the exact same problem. So:

// solve(amount) = fewest coins to make `amount`, or INF if impossible.
// Leap of faith: assume solve(smaller) is already correct.
int solve(int amount, int[] coins) {
    if (amount == 0) return 0;          // base case: nothing owed, 0 coins
    if (amount < 0)  return INF;         // overshot — this path is invalid
    int best = INF;
    for (int c : coins) {
        int sub = solve(amount - c, coins);   // solve the rest
        if (sub != INF) best = Math.min(best, 1 + sub);  // +1 for coin c
    }
    return best;
}

That's the whole brute force — and notice we derived it from "which coin next?", not from a formula. The recurrence is just the loop: solve(a) = min over coins c of ( 1 + solve(a − c) ).

Step 3 · Spot the repeated work#

Does solve(2) get called more than once? Absolutely: the path 6→4→2 reaches it, and so does 6→3→2(via −1)… and dozens more as the tree fans out. Same argument, recomputed from scratch each time. Overlapping subproblems confirmed → memoize.

Step 4 · Read the state#

What argument does solve vary over? Just amount. So the state is a single integer, 0…6, and dp[a] = fewest coins to make a. One dimension. We didn't choose that — the recursion's signature told us.

Step 5 · Memoize (top-down)#

Integer[] memo;   // memo[a] = cached answer for amount a
int solve(int amount, int[] coins) {
    if (amount == 0) return 0;
    if (amount < 0)  return INF;
    if (memo[amount] != null) return memo[amount];   // cache hit — the whole point
    int best = INF;
    for (int c : coins) if (amount - c >= 0) {
        int sub = solve(amount - c, coins);
        if (sub != INF) best = Math.min(best, 1 + sub);
    }
    return memo[amount] = best;                       // cache before returning
}

Step 6 · Tabulate (bottom-up), and watch it fill#

The table version fills dp[0], dp[1], …, dp[6] in order — each cell using only smaller, already-computed cells. Step through it below. Before each step, predict the value. The dependencies it reads (dp[a−1], dp[a−3], dp[a−4]) light up in blue.

// Bottom-up: same recurrence, now as a loop.
int coinChange(int[] coins, int amount) {
    int INF = amount + 1;                     // "impossible" sentinel > any real answer
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                                // base case: 0 coins make amount 0
    for (int a = 1; a <= amount; a++) for (int c : coins) if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);   // read smaller subproblems
    return dp[amount] > amount ? -1 : dp[amount];
}

int climbStairs(int n) {
    int a = 1, b = 1;               // ways(0), ways(1)
    for (int i = 2; i <= n; i++) {  // dp[i] only needs the last two → O(1) space
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

Another full derivation: House Robber (with a dead end)#

Problem: houses in a row with values [2, 7, 9, 3, 1]; can't rob adjacent houses; maximize loot. Let's run the engine and — crucially — hit a dead end first, because that's what really happens.

Step 1 — 2 · The choice and recursion#

At house i: rob it or skip it. If I rob it, I earn nums[i] but can't rob i−1. If I skip it, I move to i−1 with no earnings. So the recursion is:

int solve(int i, int[] nums) {
    if (i < 0) return 0;                      // no houses left
    int rob  = nums[i] + solve(i - 2, nums);   // rob i, skip i-1
    int skip = solve(i - 1, nums);              // skip i
    return Math.max(rob, skip);
}

Step 3 · Spot the repeated work#

Does solve(2) repeat? Yes — the path 4→2 reaches it (skip house 3), and so does 3→2 (skip house 4, then... wait, solve(3) calls solve(2) via skip). Same argument, recomputed. Overlaps confirmed → memoize.

Step 4 · Read the state — and hit the dead end#

Here's where beginners get stuck. They define dp[i] = "maximum loot from houses 0..i" and write:

The real dead end for House Robber comes when you add a cooldown (Stock with Cooldown pattern): then dp[i] alone is insufficient — you need to know whether you're holding. We'll see that in §05's hidden-state examples. The takeaway: even a "simple" 1D DP has a wrong version that omits a choice. Always enumerate all options at the decision point.

Step 5 — 7 · Memoize, tabulate, shrink#

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;                 // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = Math.max(prev1, x + prev2); // skip vs rob
        prev2 = prev1; prev1 = cur;           // slide the window
    }
    return prev1;
}

Because dp[i] reads only dp[i−1] and dp[i−2], two variables replace the whole array. O(n) time, O(1) space — the full pipeline, start to finish.

A third derivation: Word Break (greedy fails, then DP)#

Problem: given a string s = "leetcode" and a dictionary ["leet", "code"], can you segment s into space-separated dictionary words? Let's run the engine.

Detour: why greedy fails#

Step 1 — 2 · The choice and recursion#

At position i in the string: which dictionary word starts here? If word w matches s[i..i+len(w)), then the rest is solve(i + len(w)). If any choice leads to the end, the answer is true.

boolean solve(int i, String s, Set<String> dict) {
    if (i == s.length()) return true;         // reached the end — segmented!
    for (String w : dict) {
        if (i + w.length() <= s.length() && s.substring(i, i + w.length()).equals(w)) if (solve(i + w.length(), s, dict))  // leap of faith
        return true;
    }
    return false;
}

Step 3 · Spot the repeated work#

Does solve(j) repeat for the same j via different word choices? Absolutely — two different words might land at the same position j from different starting points. Same suffix, recomputed. Overlaps confirmed → memoize.

Step 4 · Read the state#

The only argument is i (position in the string). State = a single index 0..n. dp[i] = can we segment s[i..]? One dimension, boolean DP.

Step 5 — 6 · Memoize and tabulate#

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[s.length()] = true;                     // base: empty suffix is segmentable
    for (int i = s.length() - 1; i >= 0; i--)  // fill right-to-left
    for (String w : dict) if (i + w.length() <= s.length() && s.substring(i, i + w.length()).equals(w) && dp[i + w.length()])       // the remainder is solvable
    { dp[i] = true; break; }
    return dp[0];
}

05 · State design#

State is the scariest word in DP and the most over-mystified. Here is the whole truth:

Where dimensions come from#

Each independent "fact you must carry" is one dimension. You add a dimension only when the future genuinely depends on that fact.

The three state diseases (and their cures)#

How to know your state is right — the sufficiency test#

A state is correct iff it satisfies the Markov property for your problem: given the state, the optimal continuation does not depend on how you got there. Concretely, run this check:

• Take two different histories that land in the same state.
• Ask: from here on, would the best decisions differ?
• If they'd differ → state is missing a dimension (hidden state). If they're always identical → your state is sufficient.

State design pitfalls — three wrong states, diagnosed and fixed#

The sufficiency test is useless without practice. Here are three real problems where the "obvious" state is wrong. For each: the wrong state, the symptom, the diagnosis, and the fix.

06 · Transition design#

The transition is how a state's answer is built from smaller states' answers. People treat transitions as arcane. They're not — they're just your Step-1 choice, written as an equation. If you can list the options at one step, you can write the transition.

Deriving a transition, live: House Robber#

Problem: houses in a row with values; robbing adjacent houses trips the alarm; maximize loot. State: dp[i] = max loot considering houses 0..i. What's the choice at house i?

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;                 // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = Math.max(prev1, x + prev2); // skip vs rob — the transition
        prev2 = prev1; prev1 = cur;           // slide the window (Step 7 space cut)
    }
    return prev1;
}

07 · Base cases — discovered, not guessed#

Base cases feel fiddly because people reverse-engineer them. Do it forward instead: a base case is the smallest input where the answer is obvious without any recursion. It's wherever your recursion bottoms out.

08 · Memoization vs Tabulation#

These are two ways to run the same recurrence. They compute identical values; they differ in who drives the order.

The 5-step mechanical conversion: memo → table#

Converting is a checklist, not a creative act:

Integer[] memo;
int fib(int n) {
  if (n <= 1) return n;          // base
  if (memo[n] != null) return memo[n];            // cache
  return memo[n] = fib(n-1) + fib(n-2);       // recurrence
}

int fib(int n) {
  if (n <= 1) return n;
  int[] dp = new int[n+1];
  dp[0] = 0; dp[1] = 1;          // base seeds (step 2)
  for (int i = 2; i <= n; i++)   // order: needs i-1,i-2 → ascending (step 3)
    dp[i] = dp[i-1] + dp[i-2]; // same recurrence (step 4)
  return dp[n];                  // goal (step 5)
}

09 · Space optimization — why it's allowed#

Everyone learns "just keep two rows." Nobody explains why it's legal. Here's the principle, and once you have it you'll derive the trick yourself instead of memorizing it per-problem.

int[] dp = new int[W+1];
for (int i = 0; i < n; i++)
  for (int w = W; w>= wt[i]; w--)   // ↓ each item once
     dp[w] = Math.max(dp[w], val[i] + dp[w-wt[i]]);

int[] dp = new int[W+1];
for (int i = 0; i < n; i++)
  for (int w = wt[i]; w <= W; w++)   // ↑ reuse allowed
     dp[w] = Math.max(dp[w], val[i] + dp[w-wt[i]]);

09b · Path reconstruction — recovering the actual solution#

So far every DP returns a number: the min cost, the count, the length. But interviews frequently ask "return the actual sequence" — which coins, which path, which words. Here's how to get the solution, not just its measure.

Worked example: Coin Change — recover which coins#

Recall dp[a] = min coins to make amount a. We add a parallel array usedCoin[a] that stores which coin was picked to achieve dp[a].

int coinChangeWithPath(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    int[] usedCoin = new int[amount + 1];      // which coin achieved dp[a]
    Arrays.fill(dp, INF);
    Arrays.fill(usedCoin, -1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) for (int c : coins) if (c <= a && 1 + dp[a - c] < dp[a]) {
        dp[a] = 1 + dp[a - c];
        usedCoin[a] = c;                // remember the choice
    }
    if (dp[amount] > amount) return -1;

    // Walk back from the goal to the base, collecting coins
    List<Integer> path = new ArrayList<>();
    int a = amount;
    while (a > 0) {
        path.add(usedCoin[a]);                  // the coin chosen at this step
        a -= usedCoin[a];                       // go to the subproblem it came from
    }
    Collections.reverse(path);                  // we collected backwards
    System.out.println("Coins used: " + path);  // e.g. [3, 3] for amount 6
    return dp[amount];
}

Worked example: LCS — recover the actual subsequence#

For 2D tables, from[i][j] records which predecessor was chosen: diagonal (match), up, or left. Walk from dp[n][m] back to dp[0][0].

String lcsPath(String A, String B) {
    int n = A.length(), m = B.length();
    int[][] dp = new int[n+1][m+1];
    int[][] from = new int[n+1][m+1];  // 0=diag(match), 1=up, 2=left
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        if (A.charAt(i-1) == B.charAt(j-1)) {
            dp[i][j] = 1 + dp[i-1][j-1];
            from[i][j] = 0;                // diagonal — this char is in the LCS
        } else if (dp[i-1][j] >= dp[i][j-1]) {
            dp[i][j] = dp[i-1][j];
            from[i][j] = 1;                // came from above
        } else {
            dp[i][j] = dp[i][j-1];
            from[i][j] = 2;                // came from left
        }
    }
    // Walk back from (n,m) to (0,0), collecting chars on diagonal moves
    StringBuilder sb = new StringBuilder();
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (from[i][j] == 0) {                  // match — this char is in the LCS
            sb.append(A.charAt(i-1));
            i--; j--;
        } else if (from[i][j] == 1) i--;       // came from above, move up
        else j--;                               // came from left, move left
    }
    return sb.reverse().toString();             // collected backwards
}

10 · Twelve families that cover ~95% of DP#

Learn these state shapes and most DP problems become "oh, it's a variant of X." The remaining 5% are combinations of two of these.

int linear(int[] a) {
    int n = a.length;
    int[] dp = new int[n + 1];
    dp[0] = base;                      // smallest subproblem
    for (int i = 1; i <= n; i++) dp[i] = combine(dp[i-1], dp[i-2], a[i-1]);   // your transition
    return dp[n];
}

// max value, each item used at most once
int knapsack01(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];                 // dp[c] = best value at capacity c
    for (int i = 0; i < wt.length; i++) for (int c = W; c>= wt[i]; c--)        // DESCENDING → each item once
    dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);
    return dp[W];
}

for (int i = 0; i < wt.length; i++)
    for (int c = wt[i]; c <= W; c++)            // ASCENDING → reuse allowed
dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);

int lcs(String A, String B) {
    int n = A.length(), m = B.length();
    int[][] dp = new int[n + 1][m + 1];        // row/col 0 = empty prefix = 0
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j] = A.charAt(i-1) == B.charAt(j-1) ? 1 + dp[i-1][j-1]              // match → take both, go diagonal
    : Math.max(dp[i-1][j], dp[i][j-1]); // mismatch → drop one
    return dp[n][m];
}

int minPathSum(int[][] g) {
    int m = g.length, n = g[0].length;
    int[][] dp = new int[m][n];
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
        if (r == 0 && c == 0) dp[r][c] = g[r][c];                 // start
        else {
            int up   = r > 0 ? dp[r-1][c] : Integer.MAX_VALUE;    // from above
            int left = c > 0 ? dp[r][c-1] : Integer.MAX_VALUE;    // from left
            dp[r][c] = g[r][c] + Math.min(up, left);
        }
    }
    return dp[m-1][n-1];
}

// dp[i][j] over ranges, filled by increasing length
for (int len = 2; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
    int j = i + len - 1;
    dp[i][j] = INF;
    for (int k = i; k < j; k++)             // split [i..j] at k | k+1
    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + costToMerge(i, k, j));
    }
return dp[0][n-1];

// returns {robThis, skipThis} for the subtree rooted at node
int[] dfs(TreeNode node) {
    if (node == null) return new int[]{0, 0};
    int[] L = dfs(node.left), R = dfs(node.right);
    int rob  = node.val + L[1] + R[1];              // take node → children skipped
    int skip = Math.max(L[0], L[1]) + Math.max(R[0], R[1]); // free to take or not
    return new int[]{rob, skip};
}
int rob(TreeNode root) { int[] r = dfs(root); return Math.max(r[0], r[1]); }

// dp[mask][i] = min cost to visit set `mask`, currently at city i
int[][] dp = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;                                   // started at city 0
for (int mask = 1; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++) {
    if ((mask & (1 << i)) == 0 || dp[mask][i] == INF) continue;
    for (int j = 0; j < n; j++)             // go to an unvisited city j
    if ((mask & (1 << j)) == 0) dp[mask | (1 << j)][j] = Math.min(dp[mask | (1 << j)][j], dp[mask][i] + cost[i][j]);
    }

int[] digits; Integer[][] memo;   // memo[pos][property]; index tight separately
// pos: current digit index; tight: bounded by N's prefix; ... : property state
int go(int pos, boolean tight, int prop) {
    if (pos == digits.length) return isGood(prop) ? 1 : 0;
    if (!tight && memo[pos][prop] != null) return memo[pos][prop]; // cache only when free
    int limit = tight ? digits[pos] : 9;
    int total = 0;
    for (int d = 0; d <= limit; d++) total += go(pos + 1, tight && (d == limit), nextProp(prop, d));
    if (!tight) memo[pos][prop] = total;
    return total;
}

// dp[i][j] = max (myScore - oppScore) the mover can secure on piles [i..j]
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = piles[i];      // one pile: take it
for (int len = 2; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
    int j = i + len - 1;
    dp[i][j] = Math.max(                          // I move, then opponent's dp is subtracted
    piles[i] - dp[i+1][j],                    // take left
    piles[j] - dp[i][j-1]);                   // take right
    }
return dp[0][n-1] > 0;   // first player wins iff positive margin

// dp[k][r][c] = prob of still being on-board after k moves from (r,c)
double knightProbability(int N, int K, int r, int c) {
    double[][] prob = new double[N][N];
    prob[r][c] = 1.0;
    int[][] moves = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
    for (int step = 0; step < K; step++) {
        double[][] next = new double[N][N];
        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (prob[i][j]> 0) for (int[] m : moves) {
            int ni = i+m[0], nj = j+m[1];
            if (ni>=0 && ni<N && nj>=0 && nj<N) next[ni][nj] += prob[i][j] / 8.0;   // weighted by 1/8
        }
        prob = next;
    }
    double sum = 0;
    for (double[] row : prob) for (double p : row) sum += p;
    return sum;
}

boolean wordBreak(String s, List<String> dict) {
    Set<String> words = new HashSet<>(dict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[s.length()] = true;                       // empty suffix = segmentable
    for (int i = s.length() - 1; i >= 0; i--) for (String w : words) if (i + w.length() <= s.length() && s.startsWith(w, i) && dp[i + w.length()]) { dp[i] = true; break; }
    return dp[0];
}

int minCut(String s) {
    int n = s.length();
    boolean[][] pal = isPalTable(s);             // pal[i][j] = is s[i..j] palindrome?
    int[] dp = new int[n];                       // dp[i] = min cuts for s[0..i]
    Arrays.fill(dp, Integer.MAX_VALUE);
    for (int i = 0; i < n; i++) {
        if (pal[0][i]) { dp[i] = 0; continue; }  // whole prefix is palindrome
        for (int j = 0; j < i; j++) if (pal[j+1][i])                     // if s[j+1..i] is palindrome
        dp[i] = Math.min(dp[i], dp[j] + 1);
    }
    return dp[n-1];
}

int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();   // tails[i] = smallest tail of an IS of length i+1
    for (int x : nums) {
        int pos = Collections.binarySearch(tails, x);
        if (pos < 0) pos = -(pos + 1);            // insertion point
        if (pos == tails.size()) tails.add(x);    // x extends the longest IS
        else tails.set(pos, x);                   // x improves a shorter IS's tail
    }
    return tails.size();
}

int splitArray(int[] nums, int k) {
    long lo = maxElement(nums), hi = sumOf(nums);  // answer is in [max, sum]
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (canSplit(nums, k, mid))               // can we split into ≤ k parts with max sum ≤ mid?
        hi = mid;                              // yes → try smaller
        else lo = mid + 1;                          // no → need larger budget
    }
    return (int) lo;
}
boolean canSplit(int[] nums, int k, long maxSum) {
    int parts = 1; long running = 0;
    for (int x : nums) {
        if (running + x > maxSum) { parts++; running = x; }
        else running += x;
    }
    return parts <= k;
}

11 · Java templates#

Skeletons for every shape. Fill in base, the choices, and the combine operator — the structure never changes.

Top-down memoization — the universal starting point#

// Generic 1-parameter memoized DP. Replace types/logic as needed.
Integer[] memo;                        // sized to the state range; null = "not computed"

int solve(int i, int[] input) {
    if (isBase(i)) return baseValue;    // smallest subproblem, answer known outright
    if (memo[i] != null) return memo[i];// cache hit — never recompute
    int best = IDENTITY;                // 0 for count, +INF for min, -INF for max
    for (Choice ch : choicesAt(i))      // enumerate the ONE-STEP options
    best = combine(best, cost(ch) + solve(next(i, ch), input));
    return memo[i] = best;              // cache before returning
}
// caller: Arrays.fill(memo, null); return solve(start, input);

2D memoization (two-index / knapsack / alignment)#

Integer[][] memo;                      // memo[i][j]
int solve(int i, int j) {
    if (base) return baseValue;
    if (memo[i][j] != null) return memo[i][j];
    int best = IDENTITY;
    // ... combine over the few transitions that read solve(i-1,j), solve(i,j-1), solve(i-1,j-1) ...
    return memo[i][j] = best;
}

Bottom-up 1D tabulation#

int[] dp = new int[n + 1];
dp[0] = base;                                  // seed base case(s)
for (int i = 1; i <= n; i++) {                 // order: dependencies (i-1,i-2) already done
    int best = IDENTITY;
    for (Choice ch : choicesAt(i)) best = combine(best, cost(ch) + dp[prev(i, ch)]);
    dp[i] = best;
}
return dp[n];

Bottom-up 2D tabulation#

int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = baseCol(i);   // seed first column
for (int j = 0; j <= m; j++) dp[0][j] = baseRow(j);   // seed first row
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] /*, current*/);
return dp[n][m];

State compression — 2D → two rows → one row#

// When dp[i][*] only reads dp[i-1][*]: keep one row and update in place.
int[] dp = new int[m + 1];
seedFirstRow(dp);
for (int i = 1; i <= n; i++) {
    // iterate j in the direction that preserves the values you still need:
    //   ascending if you may reuse the current row (unbounded);
    //   descending if each layer must use only the previous row (0/1).
    for (int j = ...; ...; ...) dp[j] = combine(dp[j], dp[jPrev]);
}
return dp[m];

Helper utilities you'll reuse#

static final int INF = Integer.MAX_VALUE / 2;   // /2 avoids overflow when you do INF + x

// HashMap memo for sparse / non-integer states (e.g. encoded tuples or masks)
Map<Long, Integer> memo = new HashMap<>();
long key(int a, int b) { return ((long) a << 20) | b; }   // pack two small ints

// path reconstruction: keep a parent/choice table alongside dp, then walk it back
int[] from = new int[n + 1];
// ...set from[i] = chosenPrev when you update dp[i]...
// then follow `from` from the goal state back to the base to recover the actual solution

12 · Debugging DP#

DP bugs are silent — you get a number, it's just wrong. Here's how to find the lie fast.

amount:   0   1   2   3   4   5   6
dp[]:     0   1   2   1   1   2   2
                  ^           ^
          dp[2]=2 (1+1)   dp[5]=2 (4+1 or 1+4)
          dp[6]=2 = 1 + dp[3] = 1 + dp[2]?  → min(1+dp[5], 1+dp[3], 1+dp[2]) = min(3,2,3)=2  ✓

If your dp[6] printed 3 instead of 2, you'd immediately look at which coins the transition considered — and discover it forgot the coin 3 branch. The table doesn't lie; read it.

Worked debugging example: wrong loop direction in 1D knapsack#

You're solving Coin Change II (count the number of combinations to make amount 5 with coins {1, 2, 5}). The correct answer is 4: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}. Your code returns 9. Let's debug by reading the table.

amount:   0   1   2   3   4   5
dp[]:      1   1   2   3   5   9
                         ^???
     expected dp[5] = 4, got 9 — DOUBLE-COUNTED

Step through the diagnosis: dp[0] = 1 (one way to make 0: the empty set) is correct — the base case is fine. But dp[2] = 2 when it should be 2 (hmm, that's right: {1,1} and {2})... wait, the real bug shows at dp[3] = 3: {1,1,1}, {1,2}, {2,1} — three arrangements, but only two combinations. The ascending loop let each coin be reused within the same item's pass, counting {1,2} and {2,1} as different. The fix: iterate w descending so each coin is used at most once per pass. After the fix, dp[5] = 4 — exactly the four combinations. The table told you the bug was in what the loop was counting, not in the base cases.

amount:   0   1   2   3   4   5
dp[]:      1   1   2   2   3   4   ✓

13 · Interview thinking — the monologue, on a real problem#

Abstract advice doesn't stick. Here's the full internal narration of someone solving Decode Ways (LeetCode medium: "a string of digits, '1'→'A', '26'→'Z', count the number of ways to decode it") — including the wrong turns, because that's what really happens. Notice: they never "recall the formula." They run the engine out loud, hit a dead end, back up, and try again. Steal this script.

Integer[] memo;
int numDecodings(String s) {
    memo = new Integer[s.length() + 1];
    return solve(0, s);
}
int solve(int i, String s) {
    if (i == s.length()) return 1;              // base: empty suffix
    if (memo[i] != null) return memo[i];
    int ways = 0;
    if (s.charAt(i) != '0')                     // 1-digit: valid if not '0'
    ways += solve(i + 1, s);
    if (i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i+1) <= '6'))) ways += solve(i + 2, s);                 // 2-digit: valid if 10–26
    return memo[i] = ways;
}

14 · The problem roadmap#

Order matters. Each rung teaches one new idea on top of the last. Don't skip — the "why next" is the point. Do all of a tier before the next.

Tier 0 · Feel the recurrence easy#

1. Fibonacci Number↗ The literal "cache a recursion" exercise. Do it memoized, then bottom-up, then O(1) space — three forms of one idea.
2. Climbing Stairs↗ Same recurrence, but you must derive it from the problem ("how did I arrive?"). Bridges Fib → real problems.
3. Min Cost Climbing Stairs↗ Adds an objective (min) and per-step cost — your first optimization DP.

Tier 1 · The take/skip choice medium#

1. House Robber↗ Introduces a constrained choice (can't take neighbors). The prototypical 1D DP.
2. Maximum Subarray (Kadane)↗ "extend or restart" — a DP you can compress to one variable. Teaches state = "best ending here."
3. Stock with Cooldown↗ Your first hidden-state lesson — add "do I hold a share?" as a dimension. Pivotal.

Tier 2 · The 2D grid & two-sequence jump medium#

1. Unique Paths↗ → Minimum Path Sum↗ First 2D table; "predecessor" thinking. Count then min — same skeleton.
2. Longest Common Subsequence↗ Two pointers over two strings; match=diagonal vs mismatch=max. The template for a whole family.
3. Coin Change↗ Unbounded knapsack; loop-direction / reuse subtlety. The most-tested DP.
4. Partition Equal Subset Sum↗ 0/1 knapsack as feasibility; the once-vs-reuse contrast with Coin Change.

Tier 3 · Harder states & new shapes hard#

1. Longest Increasing Subsequence↗ "ending at i" state; then the O(n log n) upgrade. Two mindsets in one problem.
2. Edit Distance↗ Three-way transition; the peak of the alignment family.
3. Word Break↗ DP over string positions with a dictionary — feasibility with a twist.
4. Burst Balloons↗ Interval DP + the "resolved last" reframing. If you get this, you've arrived.

Tier 4 · Specialist families hard#

1. House Robber III↗ Tree DP with per-node state.
2. Stone Game↗ Game/minimax with the relative-score trick.
3. Partition to K Equal Sum Subsets↗ Bitmask subset DP.
4. Knight Probability↗ Probability DP with a time dimension.

Tier 5 · String DP & DP + Binary Search hard#

1. Word Break↗ Feasibility string DP — the canonical entry to string/segment family.
2. Palindrome Partitioning II↗ Two-pass: palindromic table + 1D min-cuts. Combines interval and string DP.
3. Regular Expression Matching↗ Hardest string DP — . and * with "match zero or more" semantics.
4. Split Array Largest Sum↗ BS on answer + greedy check. The canonical DP+BS combo.

15 · Cheat sheets#

Everything compressed. Screenshot these; they're the residue of the whole page.

The Discovery Engine, on one line each#

Recognition checklist — "should I reach for DP?"#

• Objective is max / min / count / feasibility over choices — not sort/search/one-value.
• You can break greedy with a small counterexample (local-best ≠ global-best).
• The answer decomposes into smaller instances of the same problem.
• The brute-force recursion re-solves the same subproblem — the confirming test.
• The future depends on only a few summarizing facts → small state.

Objective → combine operator → base value#

State shape by family#

State design decision guide — "should I add a dimension?"#

The dimension-adding checklist#

Complexity intuition#

The mistakes that cost the most points#