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

Part 12 of 16 · ~4 min

Dynamic Programming Part 2

2D DP and the knapsack shape

Each candidate elective carries a credit cost and an interest score pulled from ratings; a student has a fixed number of credits left and wants the highest total interest without going over — each elective usable once or not at all. That's 0/1 knapsack, and the "0/1" is exactly this constraint: take it once, or skip it, never twice.

Put the state into a sentence before writing the loop: dp[i][w] holds the best interest score achievable by choosing among only the first i candidates, spending no more than w credits. Each elective, when its turn comes, only ever has two moves available — leave it out, or take it if there's still room.

function bestElectivePlan(electives, creditBudget) {
  const n = electives.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(creditBudget + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    const { credits, interest } = electives[i - 1];
    for (let w = 0; w <= creditBudget; w++) {
      dp[i][w] = dp[i - 1][w];                              // option 1: skip this one
      if (credits <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - credits] + interest                 // option 2: take it
        );
      }
    }
  }
  return dp[n][creditBudget];
}

Checking every subset directly costs O(2ⁿ) — the same enumeration the backtracking chapter built, applied here. The table sidesteps it by solving every smaller budget first, so the final cell never has to redo work already sitting in an earlier row. If the school ever let a student retake an elective for extra credit, the "unbounded" version barely changes shape: the transition would pull from dp[i][...] — this same row, letting the elective repeat — instead of dp[i-1][...]. Seeing that as a one-line edit rather than a whole new problem is the actual payoff of understanding state and transition instead of memorizing the loop.

The longest-common-subsequence family

A transferring student's finished courses rarely line up exactly with a new program's required sequence — but a degree audit wants to know how much of the requirement is effectively already satisfied, in order, even with other courses interleaved between the matches:

function longestMatchingSequence(completed, required) {
  const dp = Array.from({ length: completed.length + 1 }, () => new Array(required.length + 1).fill(0));

  for (let i = 1; i <= completed.length; i++) {
    for (let j = 1; j <= required.length; j++) {
      if (completed[i - 1] === required[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;         // a match — extend the run
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);   // drop a course from either side
      }
    }
  }
  return dp[completed.length][required.length];
}

const completed = ['MATH101', 'ENG101', 'BIO110', 'CHEM110', 'PHYS101'];
const required  = ['MATH101', 'BIO110', 'PHYS101', 'STAT201'];
longestMatchingSequence(completed, required);   // 3 — MATH101, BIO110, PHYS101 line up on both sides

ENG101 and CHEM110 aren't on the required list, and STAT201 is still outstanding — but MATH101, BIO110, and PHYS101 appear in the same relative order on both sides, and that's precisely what this table finds: three requirements already effectively met, one still owed.

The same grid, with small tweaks, backs an entire family of two-sequence problems: edit distance between course-code strings (add a third option — substitute — and track a cost instead of a match count), the longest unbroken run rather than subsequence (reset to zero on any mismatch instead of taking a max, since a run can't have gaps), and transcript-diffing generally.

A general checklist for a new DP problem

Four questions, worth asking in this order before writing any code:

1. Put one table entry into a plain sentence before writing any code. ("dp[i] is the best score reachable using only the first i electives.")
2. At a given step, what are the actual options on the table, and where does picking each one land you?
3. Where does the recursion bottom out — the case small enough to answer directly, no further lookups needed?
4. In what order do the cells need filling so nothing gets read before it's been written?

Getting stuck on a transition is, almost every time, actually being stuck on question one — a state definition that isn't precise yet — rather than a math problem. Pin the state down in words first, and the transition tends to fall out as the next obvious question rather than a spark of insight.

Drill this on Dynamic Programming.