DP — Advanced (Knapsack, Interval, State Machines)

0/12 in this phase0/57 across the roadmap

📖 Concept

Advanced DP introduces more complex state representations and techniques that appear in harder interview questions.

Knapsack variants:

0/1 Knapsack — Each item used once: dp[i][w] = max(skip, take)
Unbounded Knapsack — Items reusable: coin change, rod cutting
Bounded Knapsack — Each item has a count limit
Multi-dimensional — Multiple constraints (weight AND volume)

Interval DP:

dp[i][j] = optimal answer for range [i, j]
Fill diagonally: length 1, then 2, then 3, ...
Examples: matrix chain multiplication, burst balloons, palindrome partitioning

State Machine DP:

Model problem as states with transitions
dp[i][state] = best answer at position i in given state
Examples: stock trading with cooldown, regex matching

Bitmask DP:

Use bitmask to represent subset of items visited/chosen
dp[mask][i] = best answer having visited items in mask, ending at i
Examples: traveling salesman, shortest path visiting all nodes
Works when n ≤ 20 (2²⁰ ≈ 1M states)

🏠 Real-world analogy: Advanced DP is like planning a complex trip with multiple constraints (budget, time, must-visit places). You track the best option for each combination of "places visited so far" and "budget remaining."

💻 Code Example

codeTap to expand ⛶

1// STOCK TRADING WITH COOLDOWN — State Machine DP
2function maxProfitCooldown(prices: number[]): number {
3  let hold = -prices[0], sold = 0, rest = 0;
4  for (let i = 1; i < prices.length; i++) {
5    const prevHold = hold, prevSold = sold;
6    hold = Math.max(hold, rest - prices[i]);    // Buy or keep holding
7    sold = hold + prices[i];                     // Wait... this is wrong
8    // Correct:
9    hold = Math.max(prevHold, rest - prices[i]);
10    sold = prevHold + prices[i];                 // Sell what we held
11    rest = Math.max(rest, prevSold);             // Rest or was just sold
12  }
13  return Math.max(sold, rest);
14}
15
16// BURST BALLOONS — Interval DP O(n³)
17function maxCoins(nums: number[]): number {
18  const n = nums.length;
19  const balls = [1, ...nums, 1]; // Add boundaries
20  const dp = Array.from({length: n+2}, () => new Array(n+2).fill(0));
21
22  for (let len = 1; len <= n; len++) {
23    for (let left = 1; left <= n - len + 1; left++) {
24      const right = left + len - 1;
25      for (let k = left; k <= right; k++) {
26        dp[left][right] = Math.max(dp[left][right],
27          dp[left][k-1] + balls[left-1]*balls[k]*balls[right+1] + dp[k+1][right]);
28      }
29    }
30  }
31  return dp[1][n];
32}
33
34// UNBOUNDED KNAPSACK — Rod cutting / coin change
35function rodCutting(prices: number[], n: number): number {
36  const dp = new Array(n + 1).fill(0);
37  for (let i = 1; i <= n; i++) {
38    for (let j = 0; j < prices.length; j++) {
39      if (j + 1 <= i) {
40        dp[i] = Math.max(dp[i], dp[i - (j+1)] + prices[j]);
41      }
42    }
43  }
44  return dp[n];
45}
46
47// BITMASK DP — Traveling Salesman (n ≤ 20)
48function tsp(dist: number[][]): number {
49  const n = dist.length;
50  const ALL = (1 << n) - 1;
51  const dp = Array.from({length: 1 << n}, () => new Array(n).fill(Infinity));
52  dp[1][0] = 0; // Start at city 0
53
54  for (let mask = 1; mask <= ALL; mask++) {
55    for (let u = 0; u < n; u++) {
56      if (!(mask & (1 << u)) || dp[mask][u] === Infinity) continue;
57      for (let v = 0; v < n; v++) {
58        if (mask & (1 << v)) continue; // Already visited
59        const newMask = mask | (1 << v);
60        dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
61      }
62    }
63  }
64
65  let result = Infinity;
66  for (let u = 0; u < n; u++) {
67    result = Math.min(result, dp[ALL][u] + dist[u][0]);
68  }
69  return result;
70}
71
72// PARTITION EQUAL SUBSET SUM — 0/1 Knapsack variant
73function canPartition(nums: number[]): boolean {
74  const sum = nums.reduce((a, b) => a + b, 0);
75  if (sum % 2 !== 0) return false;
76  const target = sum / 2;
77  const dp = new Array(target + 1).fill(false);
78  dp[0] = true;
79  for (const num of nums) {
80    for (let j = target; j >= num; j--) {
81      dp[j] = dp[j] || dp[j - num];
82    }
83  }
84  return dp[target];
85}

🏋️ Practice Exercise

Practice Problems:

Partition equal subset sum (0/1 knapsack)
Target sum — assign +/- to elements to reach target
Coin change II — number of combinations
Burst balloons — maximize coins (interval DP)
Matrix chain multiplication — minimize operations
Stock trading with cooldown / at most k transactions
Longest palindromic subsequence (2D DP)
Minimum cost to cut a stick (interval DP)
Shortest path visiting all nodes (bitmask DP)
Interleaving string — check if s3 is interleaving of s1 and s2

⚠️ Common Mistakes

Iterating in the wrong direction for 0/1 knapsack — must go right-to-left when using 1D array
Confusing 0/1 knapsack (each item once) with unbounded (items reusable) — different iteration order
Not recognizing state machine DP — keywords: 'state', 'cooldown', 'at most k transactions'
Bitmask DP only works for n ≤ ~20 due to 2ⁿ states — don't try with n = 100
Interval DP: filling in wrong order — must fill by increasing length, not row by row

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for DP — Advanced (Knapsack, Interval, State Machines)

Was this topic helpful?

← PreviousDP — 2D Problems (Grid, LCS, Edit Distance)Next →Memoization vs Tabulation — Deep Comparison