Classic DP Problems (Fibonacci, Knapsack, Longest Common Subsequence)

Classic Dynamic Programming Problems

The best way to get comfortable with Dynamic Programming is to see it in action. Let's explore how the DP principles apply to some classic problems.

---

1. Fibonacci Sequence

The Fibonacci sequence is the canonical example of a problem with overlapping subproblems. The recurrence is Fib(n) = Fib(n-1) + Fib(n-2).

• Tabulation (Bottom-Up): This is the most efficient way to solve it, using an array to store previous results.

  function fibonacci(n) {
    if (n <= 1) return n;
  
    const dp = [0, 1];
  
    for (let i = 2; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }
  
    return dp[n];
  }
  

  This can be further optimized to O(1) space by only storing the last two values.

---

2. 0/1 Knapsack Problem

This is a famous optimization problem. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. In the 0/1 version, you can either take an item or leave it.

• State: dp[i][w] represents the maximum value that can be obtained using the first i items with a maximum weight capacity of w.

• Recurrence: For each item i, we have two choices:

  1. Don't include item i: The value is the same as the best we could do with the first i-1 items: dp[i-1][w].
  2. Include item i (if it fits): The value is values[i-1] plus the best we could do with the remaining capacity: values[i-1] + dp[i-1][w - weights[i-1]].

  The recurrence is: dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])

• Implementation (Tabulation):

  function knapsack(weights, values, W) {
    const n = weights.length;
    const dp = Array(n + 1).fill(0).map(() => Array(W + 1).fill(0));
  
    for (let i = 1; i <= n; i++) {
      for (let w = 0; w <= W; w++) {
        // If the current item's weight is more than the capacity, we can't include it.
        if (weights[i - 1] > w) {
          dp[i][w] = dp[i - 1][w];
        } else {
          // Otherwise, we choose the max of including or not including the item.
          dp[i][w] = Math.max(
            dp[i - 1][w], // Don't include
            values[i - 1] + dp[i - 1][w - weights[i - 1]] // Include
          );
        }
      }
    }
    return dp[n][W];
  }
  

---

3. Longest Common Subsequence (LCS)

Given two sequences, find the length of the longest subsequence present in both of them.

• State: dp[i][j] is the length of the LCS of the first i characters of string s1 and the first j characters of string s2.

• Recurrence:

  1. If s1[i-1] is equal to s2[j-1], the characters match. The LCS is one character longer than the LCS of the strings without these last characters: 1 + dp[i-1][j-1].
  2. If the characters do not match, the LCS is the longer of the two possibilities: the LCS of s1 up to i-1 and s2 up to j, or the LCS of s1 up to i and s2 up to j-1: max(dp[i-1][j], dp[i][j-1]).

• Implementation (Tabulation):

  function lcs(s1, s2) {
    const n = s1.length;
    const m = s2.length;
    const dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0));
  
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= m; j++) {
        if (s1[i - 1] === s2[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[n][m];
  }
  

---

Key Takeaway: By identifying the state and the recurrence relation, many complex problems like Knapsack and LCS can be solved efficiently using a systematic, bottom-up tabulation approach.