02 — DP Patterns

0/1 Knapsack

Choose items with weight limit — each item used at most once.

// Given: weights[], values[], capacity W
// dp[i][w] = max value using first i items with capacity w
function knapsack(weights: number[], values: number[], W: number): number {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w]; // Don't take item i
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      }
    }
  }
  return dp[n][W];
}

// Space optimized (1D array, iterate w backwards)
function knapsack(weights: number[], values: number[], W: number): number {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) { // Backwards to avoid using item twice
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

Knapsack Variants

---

Longest Common Subsequence (LCS)

// dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.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 (s1[i - 1] === s2[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];
}

LCS variants: Edit Distance, Longest Common Substring, Shortest Common Supersequence.

---

Longest Increasing Subsequence (LIS)

// O(n²) DP
function lis(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1); // Each element is LIS of length 1
  
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

// O(n log n) with binary search
function lis(nums: number[]): number {
  const tails: number[] = []; // tails[i] = smallest tail of LIS of length i+1
  
  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

---

Coin Change

Minimum coins to make amount

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Count ways to make amount

function coinChangeWays(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  
  for (const coin of coins) {         // Coins in outer loop → combinations (not permutations)
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }
  return dp[amount];
}

---

Partition DP

Palindrome Partitioning (Min Cuts)

function minCut(s: string): number {
  const n = s.length;
  // isPalin[i][j] = is s[i..j] a palindrome?
  const isPalin = Array.from({ length: n }, () => new Array(n).fill(false));
  for (let len = 1; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && (len <= 2 || isPalin[i + 1][j - 1])) {
        isPalin[i][j] = true;
      }
    }
  }
  
  // dp[i] = min cuts for s[0..i]
  const dp = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    if (isPalin[0][i]) { dp[i] = 0; continue; }
    dp[i] = Infinity;
    for (let j = 1; j <= i; j++) {
      if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
    }
  }
  return dp[n - 1];
}

---

Bitmask DP

Use bitmask to represent subset state.

// Traveling Salesman Problem (TSP) — visit all cities with minimum cost
// dp[mask][i] = min cost to visit cities in mask, ending at city i
function tsp(dist: number[][]): number {
  const n = dist.length;
  const ALL = (1 << n) - 1;
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
  dp[1][0] = 0; // Start at city 0
  
  for (let mask = 1; mask <= ALL; mask++) {
    for (let u = 0; u < n; u++) {
      if (dp[mask][u] === Infinity) continue;
      if (!(mask & (1 << u))) continue;
      
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue; // Already visited
        const newMask = mask | (1 << v);
        dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
      }
    }
  }
  
  let ans = Infinity;
  for (let u = 0; u < n; u++) {
    ans = Math.min(ans, dp[ALL][u] + dist[u][0]); // Return to start
  }
  return ans;
}

---

Pattern Recognition

---

Key Takeaways

• Knapsack family: 0/1 (backwards), unbounded (forwards), subset sum (boolean)
• LCS/LIS: foundational 2D patterns; LIS has O(n log n) with binary search
• Coin change: unbounded knapsack variant; outer loop = coins for combinations
• Bitmask DP: represent subsets as integers; O(2^n × n) — works for n ≤ 20
• Recognize the pattern → apply the template → adjust for the problem