Chapter 13a — Dynamic Programming Problems

Before You Code: The State Question

The single most important skill in DP is defining the state precisely. Write it in English before writing any code.

A bad state definition: "dp[i] is related to the i-th element."
A good state definition: "dp[i] = the minimum number of coins needed to make exactly amount i."

If you can't write the state definition precisely, you can't write the recurrence. Get the state right first.

Problem 1: Climbing Stairs

LeetCode 70 — most common DP warm-up

State + recurrence in Chapter 13 §4. Here we add the follow-up: what if you can take 1, 2, or 3 stairs?

javascript

function climbStairs(n, steps = [1, 2]) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;  // one way to stay at ground: do nothing
  
  for (let i = 1; i <= n; i++) {
    for (const step of steps) {
      if (i >= step) dp[i] += dp[i - step];
    }
  }
  
  return dp[n];
}

This generalizes: steps = [1, 2, 3] allows 1, 2, or 3 stairs. dp[i] = total distinct ways to reach stair i.

Dry run with steps=[1,2], n=4:

code

dp[0]=1 (base: 1 way to be at ground)
dp[1]: step 1: dp[0]=1 → dp[1]=1
dp[2]: step 1: dp[1]=1. step 2: dp[0]=1 → dp[2]=2
dp[3]: step 1: dp[2]=2. step 2: dp[1]=1 → dp[3]=3
dp[4]: step 1: dp[3]=3. step 2: dp[2]=2 → dp[4]=5

Result: 5. (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2). ✓

Problem 2: House Robber II

LeetCode 213

Same as House Robber but houses are arranged in a circle — first and last houses are adjacent.

Key insight: If houses are in a circle, you can't rob both house 0 and house n-1. So split into two cases:

Rob from house 0 to n-2 (exclude last)
Rob from house 1 to n-1 (exclude first)

Take the max of both runs.

javascript

function rob(nums) {
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  
  function robLinear(arr) {
    let prev2 = 0, prev1 = 0;
    for (const n of arr) {
      const curr = Math.max(prev1, prev2 + n);
      prev2 = prev1;
      prev1 = curr;
    }
    return prev1;
  }
  
  return Math.max(
    robLinear(nums.slice(0, nums.length - 1)),
    robLinear(nums.slice(1))
  );
}

Why this works: The circular constraint says "not both 0 and n-1." The two cases cover all valid solutions: solutions that don't include house n-1 (case 1) and solutions that don't include house 0 (case 2). Every valid solution fits one of these cases. ✓

Problem 3: Coin Change II (Count Ways)

LeetCode 518

Coins [1, 2, 5] and amount 5. How many distinct combinations make amount 5? (Order doesn't matter: 1+1+3 and 1+3+1 count as one.)

This is unbounded knapsack for counting.

State: dp[i] = number of distinct combinations that sum to i.
Recurrence: For each coin c: dp[i] += dp[i - c].
Why this avoids duplicates (unlike naive nested loops)? We iterate coins in the outer loop and amounts in the inner loop. This ensures each combination is counted once in sorted order.

javascript

function change(amount, coins) {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;  // one way to make 0: use no coins
  
  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }
  
  return dp[amount];
}

Dry run on coins=[1,2,5], amount=5:

code

Initial: dp=[1,0,0,0,0,0]

Coin 1:
  i=1: dp[1] += dp[0] = 1
  i=2: dp[2] += dp[1] = 1
  i=3: dp[3] += dp[2] = 1
  i=4: dp[4] += dp[3] = 1
  i=5: dp[5] += dp[4] = 1
  dp=[1,1,1,1,1,1]

Coin 2:
  i=2: dp[2] += dp[0] = 1+1 = 2 (11 and 2)
  i=3: dp[3] += dp[1] = 1+1 = 2 (111, 12)
  i=4: dp[4] += dp[2] = 1+2 = 3 (1111, 112, 22)
  i=5: dp[5] += dp[3] = 1+2 = 3 (11111, 1112, 122)
  dp=[1,1,2,2,3,3]

Coin 5:
  i=5: dp[5] += dp[0] = 3+1 = 4 (11111, 1112, 122, 5)
  dp=[1,1,2,2,3,4]

Result: dp[5] = 4. ✓ Combinations: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}.

Why coins outer, amount inner avoids order permutations? If we did amount outer and coins inner, we'd count [1,2] and [2,1] as separate combinations. With coins outer, when we're processing coin 2, we only build on top of solutions already constructed from coin 1 (and coin 2 itself) — never mixing order.

Problem 4: Word Break

LeetCode 139

Given string s = "leetcode" and dictionary wordDict = ["leet", "code"], return true if s can be segmented into dictionary words.

State: dp[i] = can the first i characters of s be segmented?
Recurrence: dp[i] = true if there exists some j < i where dp[j] === true AND s[j..i-1] is in the dictionary.
Base case: dp[0] = true (empty string is always valid).

javascript

function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;  // found one valid split, no need to check further
      }
    }
  }
  
  return dp[n];
}

Full dry run on s="leetcode", dict=["leet","code"]:

code

n=8, dp=[T,F,F,F,F,F,F,F,F]

i=1: j=0: dp[0]=T, s[0..0]="l" in dict? No → dp[1]=F
i=2: j=0: s[0..1]="le"? No. j=1: dp[1]=F → dp[2]=F
i=3: similar, dp[3]=F
i=4: j=0: dp[0]=T, s[0..3]="leet"? YES → dp[4]=T
i=5: j=0: s[0..4]="leetc"? No. j=1..3: dp=F. j=4: dp[4]=T, s[4..4]="c"? No → dp[5]=F
i=6: j=4: dp[4]=T, s[4..5]="co"? No → dp[6]=F
i=7: j=4: s[4..6]="cod"? No → dp[7]=F
i=8: j=4: dp[4]=T, s[4..7]="code"? YES → dp[8]=T

Result: true. ✓ Segmented as "leet" + "code".

Time: O(n² × L) where L is average word length for the slice + hash check. Optimized with a Trie to O(n²) total.

Problem 5: Unique Paths

LeetCode 62

An m×n grid. Robot starts at top-left, can only move right or down. How many unique paths to bottom-right?

State: dp[i][j] = number of paths to reach cell (i, j).
Recurrence: You can only arrive from above (i-1, j) or from the left (i, j-1). So dp[i][j] = dp[i-1][j] + dp[i][j-1].
Base cases: dp[0][j] = 1 for all j (only one way along the top row: keep going right). dp[i][0] = 1 for all i (only one way along the left column: keep going down).

javascript

function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  
  return dp[m - 1][n - 1];
}

Table for m=3, n=3:

code

1  1  1
1  2  3
1  3  6

Result: 6. ✓ (The grid forms Pascal's triangle rotated.)

Mathematical insight: This equals C(m+n-2, m-1) — the number of ways to choose which m-1 of the m+n-2 total moves are "down" moves. But the DP is cleaner and handles obstacles (LeetCode 63) naturally.

Problem 6: Longest Common Subsequence (with reconstruction)

LeetCode 1143

Full solution in Chapter 13 §6. Here we add reconstructing the actual LCS, not just its length.

After filling the DP table, trace back from dp[m][n]:

javascript

function lcs(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i-1] === text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  
  // Reconstruct
  let i = m, j = n;
  const result = [];
  while (i > 0 && j > 0) {
    if (text1[i-1] === text2[j-1]) {
      result.push(text1[i-1]);
      i--; j--;
    } else if (dp[i-1][j] > dp[i][j-1]) {
      i--;
    } else {
      j--;
    }
  }
  
  return result.reverse().join('');
}

Trace for "abcde" vs "ace":

code

dp table (from Ch 13):
        ""  a  c  e
  ""  [ 0, 0, 0, 0]
  a   [ 0, 1, 1, 1]
  b   [ 0, 1, 1, 1]
  c   [ 0, 1, 2, 2]
  d   [ 0, 1, 2, 2]
  e   [ 0, 1, 2, 3]

Trace from dp[5][3]=3:
  i=5,j=3: text1[4]='e'===text2[2]='e' → push 'e', i=4,j=2
  i=4,j=2: text1[3]='d'≠text2[1]='c'. dp[3][2]=2 > dp[4][1]=1 → i=3
  i=3,j=2: text1[2]='c'===text2[1]='c' → push 'c', i=2,j=1
  i=2,j=1: text1[1]='b'≠text2[0]='a'. dp[1][1]=1 > dp[2][0]=0 → i=1
  i=1,j=1: text1[0]='a'===text2[0]='a' → push 'a', i=0,j=0
  loop ends

result = ['e','c','a'] → reverse → "ace" ✓

Problem 7: Edit Distance (full explanation in Ch 13 §7)

Here we add reconstruction — the actual sequence of operations:

javascript

function minDistanceOps(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m+1 }, (_, i) =>
    Array.from({ length: n+1 }, (_, j) => (i===0 ? j : j===0 ? i : 0))
  );
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i-1] === word2[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
    }
  }
  
  // Trace back operations
  const ops = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && word1[i-1] === word2[j-1]) {
      i--; j--;  // match, no op
    } else if (j === 0 || (i > 0 && dp[i-1][j] < dp[i][j-1] && dp[i-1][j] <= dp[i-1][j-1])) {
      ops.push(`delete '${word1[i-1]}' at pos ${i-1}`);
      i--;
    } else if (i === 0 || (j > 0 && dp[i][j-1] < dp[i-1][j] && dp[i][j-1] <= dp[i-1][j-1])) {
      ops.push(`insert '${word2[j-1]}' at pos ${j-1}`);
      j--;
    } else {
      ops.push(`replace '${word1[i-1]}' with '${word2[j-1]}'`);
      i--; j--;
    }
  }
  
  return { distance: dp[m][n], operations: ops.reverse() };
}

Problem 8: Burst Balloons — Interval DP

LeetCode 312 — Hard

Given nums = [3, 1, 5, 8], you burst balloons one at a time. Bursting balloon i gives nums[i-1] * nums[i] * nums[i+1] coins. Maximize total coins.

This is Interval DP — a harder pattern. The key reversal: instead of thinking "which balloon to burst first", think "which balloon to burst last in interval [i, j]."

Why reverse? If we think forward (first burst), the subproblems overlap in a complex way — the neighbors of balloon k change as other balloons burst. But if we think backward (last burst), the boundaries of the interval are fixed, making subproblems independent.

State: dp[i][j] = maximum coins from bursting all balloons in nums[i..j].
Recurrence: For each k in [i, j] as the LAST balloon to burst in this interval: dp[i][j] = max over k of (dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j])

The "last" balloon k sees its left neighbor at i-1 and right at j+1 (the boundaries that remain because k is last).

javascript

function maxCoins(nums) {
  // Add virtual boundary balloons of value 1
  nums = [1, ...nums, 1];
  const n = nums.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  
  // Process intervals by length
  for (let len = 1; len <= n - 2; len++) {
    for (let left = 1; left <= n - 1 - len; left++) {
      const right = left + len - 1;
      for (let k = left; k <= right; k++) {
        dp[left][right] = Math.max(
          dp[left][right],
          dp[left][k - 1] + nums[left - 1] * nums[k] * nums[right + 1] + dp[k + 1][right]
        );
      }
    }
  }
  
  return dp[1][n - 2];
}

Why iterate by interval length? dp[i][j] depends on dp[i][k-1] and dp[k+1][j], which are both shorter intervals. Processing shorter intervals first ensures dependencies are already computed.

Dry run on [3,1,5,8] → nums=[1,3,1,5,8,1] (with boundaries):

code

Intervals of length 1 (single balloons):
  dp[1][1]: k=1, nums[0]*nums[1]*nums[2] = 1*3*1 = 3
  dp[2][2]: 3*1*5 = 15
  dp[3][3]: 1*5*8 = 40
  dp[4][4]: 5*8*1 = 40

Intervals of length 2:
  dp[1][2]: k=1: dp[1][0](0) + 1*3*5 + dp[2][2](15) = 15+15=30
             k=2: dp[1][1](3) + 1*1*5 + dp[3][2](0) = 3+5=8
             max=30
  dp[2][3]: k=2: 0 + 3*1*8 + dp[3][3](40) = 24+40=64
             k=3: dp[2][2](15) + 3*5*8 + 0 = 15+120=135
             max=135
  dp[3][4]: k=3: 0+1*5*1+dp[4][4](40) = 5+40=45
             k=4: dp[3][3](40)+1*8*1+0 = 40+8=48
             max=48

Intervals of length 3:
  dp[1][3]: k=1: 0 + 1*3*8 + dp[2][3](135) = 24+135=159
             k=2: dp[1][1](3) + 1*1*8 + dp[3][3](40) = 3+8+40=51
             k=3: dp[1][2](30) + 1*5*8 + 0 = 30+40=70
             max=159
  dp[2][4]: ... (similar)

Intervals of length 4:
  dp[1][4]: k=1: 0+1*3*1+dp[2][4]=3+dp[2][4]
             ... best is k=1 with 167, giving dp[1][4]=167

Result: 167. ✓

This problem demonstrates that DP state design is not always obvious — the reversal insight (last burst instead of first burst) is the key to making subproblems independent.

Problem 9: Target Sum

LeetCode 494

Given nums = [1,1,1,1,1] and target 3, assign + or - to each number. Count the number of ways to reach target.

Brute force (backtracking): Try + and - for each number. O(2^n).

DP: Transform into a 0/1 knapsack counting problem.

Let S+ = sum of numbers with +, S- = sum with -.
S+ - S- = target, S+ + S- = total.
→ S+ = (total + target) / 2.

So we need to count subsets that sum to (total + target) / 2. This is exactly the 0/1 knapsack counting problem.

javascript

function findTargetSumWays(nums, target) {
  const total = nums.reduce((s, n) => s + n, 0);
  
  // Edge cases
  if ((total + target) % 2 !== 0) return 0;
  if (Math.abs(target) > total) return 0;
  
  const s = (total + target) / 2;
  const dp = new Array(s + 1).fill(0);
  dp[0] = 1;
  
  for (const num of nums) {
    // 0/1 knapsack: iterate backwards
    for (let j = s; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }
  
  return dp[s];
}

Why backwards loop? This is 0/1 knapsack — each number used at most once. Backward iteration prevents a number from being counted twice.

Dry run on [1,1,1,1,1], target=3:

code

total=5, s=(5+3)/2=4
dp = [1,0,0,0,0]

num=1: j=4 to 1
  j=4: dp[4]+=dp[3]=0 → 0
  j=3: dp[3]+=dp[2]=0 → 0
  j=2: dp[2]+=dp[1]=0 → 0
  j=1: dp[1]+=dp[0]=1 → 1
  dp=[1,1,0,0,0]

num=1 (second 1):
  j=4: dp[4]+=dp[3]=0
  j=3: dp[3]+=dp[2]=0
  j=2: dp[2]+=dp[1]=1 → 1
  j=1: dp[1]+=dp[0]=1 → 2
  dp=[1,2,1,0,0]

num=1 (third 1):
  j=4: dp[4]+=dp[3]=0
  j=3: dp[3]+=dp[2]=1 → 1
  j=2: dp[2]+=dp[1]=2 → 3
  j=1: dp[1]+=dp[0]=1 → 3
  dp=[1,3,3,1,0]

num=1 (fourth 1):
  j=4: dp[4]+=dp[3]=1 → 1
  j=3: dp[3]+=dp[2]=3 → 4
  j=2: dp[2]+=dp[1]=3 → 6
  j=1: dp[1]+=dp[0]=1 → 4
  dp=[1,4,6,4,1]

num=1 (fifth 1):
  j=4: dp[4]+=dp[3]=4 → 5
  ...
  dp=[1,5,10,10,5]

Result: dp[4] = 5. ✓

Notice: dp = [1,5,10,10,5] — this is the 5th row of Pascal's triangle! The number of ways to pick 4 from 5 elements is C(5,4)=5. The math confirms the DP. ✓

Problem 10: Longest Palindromic Subsequence

LeetCode 516

Given s = "bbbab", find the length of the longest palindromic subsequence. Answer: 4 ("bbbb").

Key insight: The longest palindromic subsequence of s is the LCS of s and its reverse.

javascript

function longestPalindromeSubseq(s) {
  const reversed = s.split('').reverse().join('');
  return lcsLength(s, reversed);
}

function lcsLength(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m+1 }, () => new Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}

Why does LCS(s, reverse(s)) give the longest palindromic subsequence?

A palindromic subsequence reads the same forwards and backwards. If we pick characters at indices i1 < i2 < ... < ik from s and those characters form a palindrome, then in reverse(s) those same characters appear in reverse order. The LCS operation finds the longest matching subsequence between both — which is exactly the palindromic subsequences.

Direct DP approach (interval DP, O(n²)):

javascript

function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  
  for (let i = 0; i < n; i++) dp[i][i] = 1;  // single char is palindrome of length 1
  
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = dp[i+1][j-1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
      }
    }
  }
  
  return dp[0][n-1];
}

Pattern Identification Cheatsheet

You see: "minimum/maximum" + "subarray/subsequence/path" → Linear DP
You see: "count ways" + "sum to target" + "each element once" → 0/1 knapsack count
You see: "count ways" + "sum to target" + "unlimited reuse" → Unbounded knapsack count
You see: "can you partition into X" → DP (often 0/1 knapsack variant)
You see: "two strings, common/transform" → 2D DP (LCS shape or Edit Distance shape)
You see: "intervals, optimal split point" → Interval DP
You see: "circular arrangement, constraint at boundary" → Split into two linear DPs

Common Mistakes

1. Forgetting the base case for dp[0]

dp[0] = 1 (coin change II, climbing stairs, word break) is almost always 1 — "one way to do nothing." Forgetting this means nothing propagates.

2. Wrong loop direction in 0/1 knapsack

Forward loop = unbounded (reuse allowed). Backward loop = 0/1 (each item once). Mixing this up gives wrong answers that look plausible.

3. Off-by-one in the state definition

"dp[i] = answer for first i characters" vs "dp[i] = answer for characters 0..i". Pick one definition and stick to it. The LCS-style (dp[i][j] covers text1[0..i-1], with i=0 being empty) adds +1 to bounds but makes base cases cleaner.

4. Not considering dp[i-1] (skip) when defining recurrence

In House Robber, students often write only dp[i] = dp[i-2] + nums[i] (always rob house i) and forget dp[i-1] (skip house i). Both choices must be compared.

5. Using Infinity-1 vs 0 for min problems

Coin change: initialize dp[1..amount] = Infinity (can't make this amount yet). Return -1 if dp[amount] === Infinity. Don't initialize to 0 or you'll always get 0 as the minimum.

Complexity Summary

Problem	States	Work/state	Time	Space
Climbing Stairs	O(n)	O(1)	O(n)	O(1)
House Robber	O(n)	O(1)	O(n)	O(1)
Coin Change	O(amount)	O(\|coins\|)	O(amount×\|coins\|)	O(amount)
Word Break	O(n)	O(n)	O(n²)	O(n)
Unique Paths	O(m×n)	O(1)	O(m×n)	O(n)
LCS	O(m×n)	O(1)	O(m×n)	O(n)
Edit Distance	O(m×n)	O(1)	O(m×n)	O(n)
LIS (DP)	O(n)	O(n)	O(n²)	O(n)
LIS (BSearch)	O(n)	O(log n)	O(n log n)	O(n)
0/1 Knapsack	O(n×W)	O(1)	O(n×W)	O(W)
Burst Balloons	O(n²)	O(n)	O(n³)	O(n²)

Final Note: You've Covered Everything

This is the last chapter of the book. Every topic that appears in 95%+ of software engineering interviews at any level — from startup to FAANG — is now covered.

The complete arc started with measuring efficiency (Big-O), built the primitives (arrays, hash maps), learned the two core traversal patterns (recursion and iteration), then systematically covered every major algorithm family. Every chapter connected backward (what built this idea) and forward (what this idea enables).

The fastest path from here to performing well in interviews:

Practice on LeetCode. For each problem, apply the four-question framework: What do I have? What do I want? What is the brute force? Where is the waste?
Write the code by hand at first (no autocomplete). Interviews are either whiteboard or a plain editor.
Dry run your code on a small example before declaring it correct. The dry run habit catches 80% of bugs.
Know your complexities. Every algorithm in this book has a "Time: / Space:" annotation. Know them cold.
Study the patterns, not the solutions. Seeing 500 LeetCode solutions teaches you 500 tricks. Understanding the 12 patterns in this book teaches you to solve any of them.