Classic Problems

Two problems appear so frequently in interviews and competitive programming that they are considered “canonical” examples of Dynamic Programming: the 0/1 Knapsack Problem and the Longest Common Subsequence (LCS). Mastering these will give you the pattern recognition skills needed for hundreds of variations.

1. The 0/1 Knapsack Problem

Problem Statement: Given N items, each with a weight W[i] and a value V[i], and a knapsack with capacity C, determine the maximum value you can carry. You cannot break items (hence “0/1”—you either take it or leave it).

Recurrence Relation

Let dp[i][w] be the maximum value using a subset of the first i items with total weight capacity w.

• Option 1 (Skip item): dp[i-1][w]
• Option 2 (Take item): V[i] + dp[i-1][w - W[i]] (only if W[i] ≤ w)

dp[i][w] = max(Option 1, Option 2)

Interactive Visualization

Visualize how the DP table is filled to solve the Knapsack problem. Items:

1. Weight: 2, Value: 3
2. Weight: 3, Value: 4
3. Weight: 4, Value: 5
4. Weight: 5, Value: 6

Knapsack Capacity: 5

[!TIP] Try it yourself: Click “Fill Table” to see the decision process. Cells turn green when an item is included, yellow when excluded but inherited.

Ready

Code Implementation: 0/1 Knapsack

// Java
public class Knapsack {
  public int knapsack(int capacity, int[] weights, int[] values, int n) {
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
      for (int w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
          dp[i][w] = Math.max(
            values[i - 1] + dp[i - 1][w - weights[i - 1]], // Take item
            dp[i - 1][w]                                  // Skip item
          );
        } else {
          dp[i][w] = dp[i - 1][w]; // Must skip
        }
      }
    }
    return dp[n][capacity];
  }
}

// Go
func Knapsack(capacity int, weights []int, values []int) int {
  n := len(weights)
  dp := make([][]int, n+1)
  for i := range dp {
    dp[i] = make([]int, capacity+1)
  }

  for i := 1; i <= n; i++ {
    for w := 1; w <= capacity; w++ {
      if weights[i-1] <= w {
        take := values[i-1] + dp[i-1][w-weights[i-1]]
        skip := dp[i-1][w]
        if take > skip {
          dp[i][w] = take
        } else {
          dp[i][w] = skip
        }
      } else {
        dp[i][w] = dp[i-1][w]
      }
    }
  }
  return dp[n][capacity]
}

---

2. Longest Common Subsequence (LCS)

Problem Statement: Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example: text1 = "abcde", text2 = "ace". LCS is "ace", length 3.

Recurrence Relation

Let dp[i][j] be the LCS length of text1[0...i-1] and text2[0...j-1].

• Match: If text1[i-1] == text2[j-1], then dp[i][j] = 1 + dp[i-1][j-1]
• No Match: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Code Implementation: LCS

// Java
public class LCS {
  public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
      char c1 = text1.charAt(i - 1);
      for (int j = 1; j <= n; j++) {
        char c2 = text2.charAt(j - 1);

        if (c1 == c2) {
          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[m][n];
  }
}

// Go
func LongestCommonSubsequence(text1 string, text2 string) int {
  m, n := len(text1), len(text2)
  dp := make([][]int, m+1)
  for i := range dp {
    dp[i] = make([]int, n+1)
  }

  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      if text1[i-1] == text2[j-1] {
        dp[i][j] = 1 + dp[i-1][j-1]
      } else {
        if dp[i-1][j] > dp[i][j-1] {
          dp[i][j] = dp[i-1][j]
        } else {
          dp[i][j] = dp[i][j-1]
        }
      }
    }
  }
  return dp[m][n]
}

---

3. Deep Dive Strategy Lab: Classic Problems

Intuition Through Analogy

Think of this chapter like budget planning across months. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?