17 — Dynamic Programming

The 23 DP questions are the highest-leverage block in the 150. They're also the most templated: nearly all are variations on six recurrences.

What DP is

Dynamic programming is recursion plus remembering.

That's genuinely it. You write a recursive solution, notice it solves the same subproblem many times, and cache the results.

Seeing the waste

Computing Fibonacci recursively:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Trace fib(5):

                  fib(5)
                /        \
           fib(4)         fib(3)
          /     \        /      \
      fib(3)  fib(2)  fib(2)   fib(1)
      /    \
  fib(2)  fib(1)

fib(3) is computed twice. fib(2) is computed three times. For fib(50) this explodes to roughly 2^50 calls.

But there are only 51 distinct subproblems — fib(0) through fib(50). Compute each once, store it, and you're at O(n):

Integer[] memo = new Integer[n + 1];

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != null) return memo[n];      // already computed — return the cache
    return memo[n] = fib(n - 1) + fib(n - 2);
}

2^50 calls → 50. That single change is dynamic programming.

The two conditions

DP applies when a problem has:

1. Optimal substructure — the answer is built from answers to smaller instances. (The best way to make 11¢ uses the best way to make some smaller amount.)
2. Overlapping subproblems — the same smaller instance is needed many times.

Without overlap you have plain recursion or divide-and-conquer (merge sort has optimal substructure but no overlap — caching gains nothing). Without optimal substructure, DP is simply unsound.

The method — always in this order

Do not try to write a table directly. Derive it.

1. Write the brute-force recursion. What choice is made at each step? Get it correct and exponential.
2. Identify the state. Which parameters actually distinguish one subproblem from another? This is the hard part, and the part interviewers grade.
3. Add memoization. One line: check the cache, compute, store.
4. Convert to bottom-up if it helps.
5. Reduce space if each row only depends on the previous one.

Steps 1–3 are enough to pass most interviews. Do them first, then optimize out loud.

A candidate who jumps straight to a table and gets an index wrong has nothing to show. A candidate who memoizes has a correct, complete solution within minutes and can then discuss improvements from a position of strength.

Template — top-down memoization

private Integer[] memo;                          // Integer[] so null means "not computed"

public int solve(int[] nums) {
    memo = new Integer[nums.length];
    return dp(nums, 0);
}

private int dp(int[] nums, int i) {
    if (i >= nums.length) return 0;              // base case
    if (memo[i] != null) return memo[i];         // cache hit

    int take = nums[i] + dp(nums, i + 2);
    int skip = dp(nums, i + 1);
    return memo[i] = Math.max(take, skip);       // compute, store, and return in one line
}

Why Integer[] rather than int[]: an int[] starts filled with zeros, and 0 is often a legitimate answer. You'd be unable to tell "not computed yet" from "computed, the answer is 0" — and would return a stale 0 forever. Integer[] starts as null, which is unambiguous.

The alternative is int[] filled with a sentinel like -1 (when -1 can't be a real answer).

For 2-D state: Integer[][] memo = new Integer[m][n]; — same idea.

Template — bottom-up

Instead of recursing down and caching on the way back, fill the table from the smallest subproblem upward:

int[] dp = new int[n + 1];
dp[0] = base;
for (int i = 1; i <= n; i++) {
    dp[i] = combine(dp[i - 1], dp[i - 2], ...);
}
return dp[n];

Size the table n + 1 and let index 0 mean "the empty case". This removes nearly every boundary special case. Adopt it by default.

Top-down vs bottom-up:

Both are O(states × transition). Write top-down first; convert if you need the space win or the recursion is too deep.

Space reduction

When dp[i] reads only dp[i-1] and dp[i-2], you don't need the whole array — just two variables:

int prev2 = 0, prev1 = 0;
for (int num : nums) {
    int cur = Math.max(prev1, prev2 + num);
    prev2 = prev1;                            // shift the window forward
    prev1 = cur;
}
return prev1;

O(n) space → O(1). The same idea reduces a 2-D table to two rows — or one row, when updates are ordered carefully.

The six recurrences

Learn these and most of the section collapses.

1. Linear scan — the Fibonacci family

dp[i] depends on a constant number of earlier entries.

// Climbing Stairs — ways to reach step i
dp[i] = dp[i - 1] + dp[i - 2];

Reading it: to reach step i, you arrived either from i-1 (a 1-step) or i-2 (a 2-step). Total ways = the sum.

// Min Cost Climbing Stairs
dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);

// House Robber — can't rob adjacent houses
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
//                 skip i        rob i (so skip i-1)

// Decode Ways — "12" decodes as "AB" or "L"
dp[i] = (oneDigitValid  ? dp[i - 1] : 0)
      + (twoDigitsValid ? dp[i - 2] : 0);

House Robber trace, nums = [2, 7, 9, 3, 1]:

Answer: 12 (rob houses 0, 2, 4). ✓

House Robber II (houses in a circle): the first and last are now adjacent, so at most one can be robbed. Run House Robber twice — once on [0, n-2], once on [1, n-1] — and take the max. Cleaner than adding a state dimension. Handle n == 1 separately.

2. Unbounded knapsack — the "coin change" family

Unlimited copies of each item allowed.

// Coin Change — fewest coins to make `amount`
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);            // sentinel LARGER than any real answer
dp[0] = 0;                               // zero coins make zero

for (int a = 1; a <= amount; a++) {
    for (int coin : coins) {
        if (coin <= a) dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
    }
}
return dp[amount] > amount ? -1 : dp[amount];

Reading the recurrence: to make amount a, try each coin as the last one used. If you use a coin of value c, you still need the best way to make a - c, plus this one coin.

Trace: coins = [1, 3, 4], amount = 6.

Answer: 2 (3 + 3). ✓ Note greedy would take 4 + 1 + 1 = 3 coins — this is the counterexample that justifies DP over greedy.

Why amount + 1 as the sentinel rather than Integer.MAX_VALUE: the line 1 + dp[a - coin] would overflow MAX_VALUE into a negative number, which then wins the Math.min and corrupts everything. amount + 1 is larger than any real answer but safe to add to.

Coin Change II — counting combinations

int[] dp = new int[amount + 1];
dp[0] = 1;                               // one way to make 0: use nothing
for (int coin : coins) {                 // coins on the OUTSIDE
    for (int a = coin; a <= amount; a++) {
        dp[a] += dp[a - coin];
    }
}
return dp[amount];

Loop order is the whole question here

Coins outer counts combinations — {1,2} is counted once. Amount outer would count permutations — {1,2} and {2,1} counted separately.

Why: with coins outer, you finish considering coin 1 entirely before coin 2 ever appears. So any combination is built in a fixed coin order and can only be generated once. With amount outer, at each amount you try every coin, so the same multiset gets assembled in multiple orders.

Being able to state that distinction is the difference between a memorized answer and an understood one.

3. 0/1 knapsack — each item used at most once

// Partition Equal Subset Sum — can a subset sum to total/2?
int total = Arrays.stream(nums).sum();
if (total % 2 != 0) return false;              // odd total: impossible. O(1) rejection

int target = total / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;                                  // sum 0 is always reachable (empty subset)

for (int num : nums) {
    for (int t = target; t >= num; t--) {      // BACKWARD — see below
        dp[t] |= dp[t - num];
    }
}
return dp[target];

Iterating capacity backwards IS the 0/1 constraint

This is the most-tested detail in the knapsack family.

Forward iteration would allow reuse. Say num = 3 and we go forward:

• dp[3] |= dp[0] → dp[3] becomes true (used one 3).
• Later, dp[6] |= dp[3] → dp[6] becomes true — but dp[3] was just set using this same 3. You've used the item twice.

Backward iteration reads only untouched values. When you compute dp[t], the value at dp[t - num] is smaller and hasn't been updated in this pass yet — so it reflects the state before this item was available. Each item contributes at most once.

That single loop direction is the only difference between the two knapsack types. Worth saying explicitly.

Target Sum in disguise: assigning +/− to each number to reach S is equivalent to choosing a positive subset P with sum(P) = (total + S) / 2. Derive the transformation aloud, then it's 0/1 knapsack — with int[] counts instead of boolean[] for the counting version.

4. Two-sequence DP — a grid over (i, j)

dp[i][j] = the answer for the first i characters of s and the first j of t.

The universal shape: if the characters match, move diagonally. If not, take the best of the neighbours.

Longest Common Subsequence

int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = 1 + dp[i - 1][j - 1];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
}
return dp[m][n];

Reading it: if the current characters match, they contribute 1 and we move past both. If not, we must skip one of them — try skipping from s (dp[i-1][j]) or from t (dp[i][j-1]) and take whichever is better.

charAt(i - 1) because the table is 1-indexed (row 0 = "empty prefix") while the string is 0-indexed.

Trace: s = "abcde", t = "ace":

Answer: 3 ("ace"). ✓

Edit Distance

for (int i = 0; i <= m; i++) dp[i][0] = i;      // delete everything from s
for (int j = 0; j <= n; j++) dp[0][j] = j;      // insert everything from t

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];   // free
        else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],              // REPLACE
                             Math.min(dp[i - 1][j],                 // DELETE from s
                                      dp[i][j - 1]));               // INSERT into s
    }
}

Memorize which neighbour means which operation — interviewers ask:

The base cases say: turning a length-i string into an empty one takes i deletions.

Same grid, different transitions

// Distinct Subsequences: how many ways does t appear as a subsequence of s?
dp[i][j] = dp[i - 1][j] + (match ? dp[i - 1][j - 1] : 0);
//         skip s[i-1]     use s[i-1] to match t[j-1]

// Interleaving String: can s3 be formed by interleaving s1 and s2?
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
        || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));

Interleaving String's i + j - 1 is the mechanic to remember: if you've consumed i characters from s1 and j from s2, you must have produced exactly i + j characters of s3 — so the next one to match is at index i + j - 1.

Reject immediately if s1.length() + s2.length() != s3.length().

Regular Expression Matching

if (p.charAt(j - 1) == '*') {
    dp[i][j] = dp[i][j - 2]                                   // use the pattern ZERO times
            || (matches(s, i, p, j - 1) && dp[i - 1][j]);      // consume one char from s
} else {
    dp[i][j] = matches(s, i, p, j) && dp[i - 1][j - 1];
}

j - 2 skips both the character and its * — "a*" is two pattern characters, and using it zero times means ignoring both.

The second branch keeps j the same (the * can match more characters) while advancing i.

This is the hardest transition in the section. Write the two cases as separate lines, not one expression.

5. Interval DP — dp[i][j] over a range, split at k

Loop by increasing interval length, so shorter intervals are already computed when needed.

Burst Balloons

Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1], and neighbours then become adjacent. Maximize the total.

Why the obvious framing fails: if you ask "which balloon do I burst first?", the two remaining sides are not independent — bursting on the left changes what the right side's neighbour is.

The insight — ask which balloon is burst LAST. If k is burst last in the range [i, j], then at that moment everything else in the range is gone, so k's neighbours are the fixed boundaries arr[i-1] and arr[j+1]. The two sides become completely independent subproblems.

int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;                        // virtual balloons of value 1 at the edges
for (int i = 0; i < n; i++) arr[i + 1] = nums[i];

int[][] dp = new int[n + 2][n + 2];
for (int len = 1; len <= n; len++) {            // by increasing LENGTH
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        for (int k = i; k <= j; k++) {          // k = the LAST balloon burst in [i, j]
            dp[i][j] = Math.max(dp[i][j],
                arr[i - 1] * arr[k] * arr[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
        }
    }
}
return dp[1][n];

The padding with 1s removes the edge cases — a balloon at the boundary multiplies by 1 rather than needing an if.

O(n³), which the n ≤ 500 constraint permits.

6. State-machine DP

When the answer depends on a mode, add a dimension for it.

Best Time to Buy and Sell Stock with Cooldown

Three states: holding a stock, just sold (cooldown tomorrow), or free to buy.

    ┌──────── buy ────────┐
    ↓                     │
  HOLD ──── sell ────→ SOLD ──── (forced wait) ────→ REST
    ↑                                                  │
    └──────────────── buy ─────────────────────────────┘

int hold = Integer.MIN_VALUE;   // best profit while holding a stock
int sold = 0;                   // best profit having just sold today
int rest = 0;                   // best profit while free to buy

for (int price : prices) {
    int prevSold = sold;                       // save BEFORE overwriting
    sold = hold + price;                       // sell what we were holding
    hold = Math.max(hold, rest - price);       // keep holding, or buy from rest
    rest = Math.max(rest, prevSold);           // stay free, or come off cooldown
}
return Math.max(sold, rest);

prevSold is mandatory. rest needs the previous iteration's sold (you can only rest the day after selling). Updating in place without saving it first would let you rest and sell on the same day — skipping the cooldown.

Draw the state diagram before coding. With the transitions on paper, the code is mechanical.

Final answer is max(sold, rest) — never hold, since ending while holding a stock means unrealized profit.

Special cases worth their own note

Longest Increasing Subsequence

// O(n²) DP
int[] dp = new int[n];
Arrays.fill(dp, 1);                             // every element alone is a subsequence of length 1
for (int i = 1; i < n; i++)
    for (int j = 0; j < i; j++)
        if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
// answer = max of dp[]

dp[i] = the length of the longest increasing subsequence ending at i. Defining it as "ending at i" rather than "within the first i" is what makes the recurrence work.

// O(n log n) — patience sorting
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
    int pos = Collections.binarySearch(tails, num);
    if (pos < 0) pos = -(pos + 1);              // convert to the insertion point
    if (pos == tails.size()) tails.add(num);    // extends the longest run
    else tails.set(pos, num);                   // improves an existing run's tail
}
return tails.size();

tails[k] = the smallest possible tail value of any increasing subsequence of length k+1. A smaller tail is always at least as good — it leaves more room for future elements.

Important honesty point: tails is not itself a valid subsequence. Only its length is meaningful. Claiming otherwise is a correctness error an interviewer will catch. Say it proactively.

Collections.binarySearch returns -(insertionPoint) - 1 when absent — hence the -(pos + 1) conversion (02).

Maximum Product Subarray

int max = nums[0], min = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
    int n = nums[i];
    int tmpMax = max;                          // save before overwriting
    max = Math.max(n, Math.max(max * n, min * n));
    min = Math.min(n, Math.min(tmpMax * n, min * n));
    best = Math.max(best, max);
}

Why track the minimum too: a large negative product becomes a large positive one when multiplied by another negative. [-2, 3, -4] — the running max after 3 is 3, but the running min is −6, and −6 × −4 = 24 is the answer. Without tracking the min you'd miss it entirely.

tmpMax must be saved because min's computation needs the old max.

Palindromic Substrings / Longest Palindromic Substring

Expand around centers beats the DP table: O(n²) time but O(1) space instead of O(n²).

private int expand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        count++;
        l--; r++;
    }
    return count;
}
// for each i: expand(s, i, i)      — odd-length centers
//             expand(s, i, i + 1)  — even-length centers

Two center types because palindromes come in two shapes: "aba" has a single-character center; "abba" has a center between two characters. 2n − 1 centers total.

Manacher's algorithm does it in O(n). Mention it exists; don't attempt it in an interview.

Word Break

Set<String> dict = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;                                   // the empty string is trivially segmentable

for (int i = 1; i <= s.length(); i++) {
    for (int j = 0; j < i; j++) {
        if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
    }
}
return dp[s.length()];

dp[i] = "can s[0..i) be segmented?" For each i, try every split point j: if the prefix up to j works and s[j..i) is a word, then i works too.

Longest Increasing Path in a Matrix

Memoized DFS on an implicit DAG.

private int dfs(int[][] matrix, int r, int c, int[][] memo) {
    if (memo[r][c] != 0) return memo[r][c];
    int best = 1;
    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= matrix.length || nc < 0 || nc >= matrix[0].length) continue;
        if (matrix[nr][nc] <= matrix[r][c]) continue;          // strictly increasing only
        best = Math.max(best, 1 + dfs(matrix, nr, nc, memo));
    }
    return memo[r][c] = best;
}

No visited set is needed — and explaining why is what the interviewer wants:

"Edges only go from smaller values to strictly larger ones, so following edges means values strictly increase. You can never return to a cell you've left — that would require a value to be less than itself. The graph is a DAG, so no cycle protection is necessary."

memo[r][c] != 0 works as the cache check because a real path length is always at least 1.

Deciding the state

The recurring interview question is "what's your state?" Work through:

1. What varies between subproblems? Position, remaining budget, a mode flag, how many of something is left.
2. Is it enough to decide the future? If two situations share a state but need different answers, the state is incomplete — add a dimension.
3. Is any of it redundant? dp[i][j] where j is always derivable from i should be dp[i].
4. How large is the table? states × transition cost is your complexity. If it exceeds the constraint budget, the state is too rich.

DP vs. greedy vs. backtracking

• Backtracking enumerates every solution. Use when the output is the enumeration, or n ≤ 20.
• DP is backtracking plus memoization. Only works when the answer is a value, not a listing — you can't cache "all the paths".
• Greedy skips the table entirely and commits to a local choice. Only valid with a proof (20).

Keep the Coin Change counterexample ready: coins = [1, 3, 4], amount = 6. Greedy takes the largest coin first: 4 + 1 + 1 = 3 coins. Optimal is 3 + 3 = 2 coins.

That one example justifies "greedy is unsafe here, so I'll use DP" faster than any abstract argument.

Complexity summary

A note on "pseudo-polynomial": knapsack complexities like O(n · sum) depend on the value of the input, not just its length. That's not truly polynomial in the input size — naming it correctly is a senior-level signal.