Dynamic Programming (Advanced)

While 1D Dynamic Programming (like Fibonacci or Climbing Stairs) uses a single array dp[i], many classic DP problems require a 2D matrix dp[i][j] because the problem depends on two varying state parameters (e.g., the current item index AND the remaining backpack capacity).

Classic Problem 1: 0/1 Knapsack

You have a backpack with a maximum capacity W. You have a list of items, each with a weight and a value. You can either take an item completely (1) or leave it (0). You cannot take fractions (This destroys the Greedy algorithm approach). What is the maximum value you can hold?

State Definition

Let dp[i][w] represent the maximum value using the first i items, with a backpack capacity of w.

State Transition (The Core Logic)

For every item i, we have two choices:

1. Exclude it: The max value is just whatever we had without this item: dp[i-1][w].
2. Include it: We gain its value, but we subtract its weight from the capacity: value[i] + dp[i-1][w - weight[i]].

The cell dp[i][w] is simply the Math.max() of those two choices!

function knapsack01(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  // Create a 2D array: (n + 1) rows, (capacity + 1) columns
  const dp: number[][] = Array(n + 1).fill(0).map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const currentWeight = weights[i - 1];
    const currentValue = values[i - 1];

    for (let w = 1; w <= capacity; w++) {
      if (currentWeight <= w) {
        // We have enough room. Should we take it or leave it?
        dp[i][w] = Math.max(
          dp[i - 1][w], // Leave it
          currentValue + dp[i - 1][w - currentWeight] // Take it
        );
      } else {
        // Item is too heavy, we MUST leave it
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  // The answer is in the bottom-right corner!
  return dp[n][capacity];
}

Classic Problem 2: Longest Common Subsequence (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence does not have to be contiguous. (e.g., "ace" is a subsequence of "abcde").

State Definition

Let dp[i][j] represent the length of the LCS of text1 up to index i and text2 up to index j.

State Transition

1. If characters match: text1[i] === text2[j]. We add 1 to the sequence and look at the strings without these characters: 1 + dp[i-1][j-1].
2. If characters do NOT match: We try ignoring the character from text1, and then try ignoring the character from text2. We take the max of both scenarios: Math.max(dp[i-1][j], dp[i][j-1]).

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  
  // +1 to handle empty string base cases
  const dp: number[][] = Array(m + 1).fill(0).map(() => 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]) {
        // Diagonal top-left + 1
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // Max of cell above OR cell to the left
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
      
    }
  }

  return dp[m][n];
}

How to Spot a DP Problem in Interviews

If the problem asks you to find the:

• Maximum or Minimum something (e.g., Minimum coins to make change)
• Total number of ways to do something (e.g., Unique paths through a grid)
• Indicates that future decisions depend on past decisions...

There is a 95% chance it requires Dynamic Programming. Always start by writing the brute-force recursive solution, then add a cache (Memoization) to instantly convert it to an optimized DP solution!