DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Dynamic Programming Part 2

2D DP and the knapsack pattern

The 0/1 knapsack problem: given items each with a weight and a value, and a capacity limit, maximize total value without exceeding capacity — each item usable at most once (that's the "0/1": take it, or don't).

State, in words first: dp[i][w] = the best value achievable using only the first i items, with capacity w available. The transition considers exactly two choices for item i: skip it, or take it (only if it fits):

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w];                               // option 1: skip 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]      // option 2: take item i
        );
      }
    }
  }
  return dp[n][capacity];
}

The "unbounded knapsack" variant — unlimited copies of each item allowed — changes almost nothing about the shape of the solution: the transition reads from dp[i][...] (the current row, allowing an item to be reused) instead of dp[i - 1][...]. Recognizing that as a one-line change, rather than a different problem entirely, is the payoff of understanding the state and transition rather than memorizing the code.

The longest-common-subsequence family

State: dp[i][j] = the length of the longest common subsequence between the first i characters of a and the first j characters of b. The transition is a straightforward case split on whether the current characters match:

function longestCommonSubsequence(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;         // characters match — extend the subsequence
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);   // skip a character from either string
      }
    }
  }
  return dp[a.length][b.length];
}

This exact grid is the backbone of an entire family of two-string DP problems: edit distance (add a third option to the transition — substitute — and change what gets tracked), longest common substring (reset to 0 on any mismatch instead of taking the max, since a substring must stay contiguous), and diffing tools generally.

A general method for defining state and transition on a new problem

A short checklist that applies to any new DP problem, in order:

1. What does one entry of the table represent, stated in plain words, before writing a single line of code? ("dp[i] = the best answer considering only the first i items.")
2. What decision gets made at each step, and what smaller subproblem does each option reduce to?
3. What's the base case — the smallest subproblem answerable without recursing any further?
4. What order must the table be filled in, so that every value a transition reads is already computed by the time it's needed?

Struggling to find a DP transition is, almost without exception, actually struggling with step one — an imprecise state definition — rather than a math problem. Get the state definition exact, in words, before touching code, and the transition tends to become the obvious next question to ask about it rather than a leap of insight.

Practice this on Code Lab: Dynamic Programming