Tables With Two Dimensions

The previous chapter's rule — write the sentence before the code — decides the table's width: one variable of history needs a row, and two variables need a grid. "The edit distance between the first i characters of a and the first j of b" mentions two prefixes, so its table is two-dimensional, its base cases are a whole row and a whole column, and every cell looks at three neighbors. Recognizing when the sentence demands a second dimension is the entire skill gap between easy DP questions and mid-level ones.

The row and column that are the base cases

Edit distance counts single-character inserts, deletes and replacements. The sentence — table[i]j is the cost of turning the first i characters of a into the first j of b — hands you the base cases for free: turning i characters into zero costs i deletions, turning zero into j costs j insertals. The empty prefix is not an edge case to handle; it is row 0 and column 0, and filling them first is what lets every other cell trust its neighbors.

for (let i = 1; i <= a.length; i++) {
  for (let j = 1; j <= b.length; j++) {
    if (a[i - 1] === b[j - 1]) {
      table[i]![j] = table[i - 1]![j - 1] as number // the last chars agree — free
    } else {
      const del = table[i - 1]![j] as number
      const ins = table[i]![j - 1] as number
      const rep = table[i - 1]![j - 1] as number
      table[i]![j] = 1 + Math.min(del, ins, rep)
    }
  }
}

The three neighbors are three stories: delete a's last character (cell above), insert b's last character (cell left), replace (diagonal). A match takes the diagonal without paying — the agreeing characters cost nothing, which is the whole reason common substructure accumulates. Note the loop runs to length inclusive: the table is (a.length + 1) × (b.length + 1) because index 0 means "nothing", and reading a[i - 1] inside is the translation between "first i characters" and the 0-based array. That off-by-one is deliberate and load-bearing; hiding it behind a helper only moves it.

} else {
  const del = table[i - 1]![j] as number
  const ins = table[i]![j - 1] as number
  const rep = table[i - 1]![j - 1] as number
  table[i]![j] = 1 + Math.(del, ins, rep)
}

Knapsack: the sentence picks a dimension to be capacity

The 0/1 knapsack — each item once, maximize value under a weight cap — has the sentence best(i, c): the best value using items from i onward with capacity c. Every item is a decision between skip (the cell below) and take (the cell diagonal by its weight):

for (let i = items.length - 1; i >= 0; i--) {
  for (let c = 0; c <= capacity; c++) {
    const skip = best[i + 1]![c] as number
    const take = c >= items[i]!.weight
      ? items[i]!.value + (best[i + 1]![c - items[i]!.weight] as number)
      : -Infinity
    best[i]![c] = Math.max(skip, take)
  }
}

The -Infinity when the item does not fit is the sentinel rule from last chapter, chosen by operator: max cannot be tempted by it. People compress this to a 1-D array walking capacity downward — valid, and half the memory — but the direction is not style: walking upward lets one item be taken twice, which silently answers the unbounded knapsack instead. If you cannot explain why the direction matters, keep the 2-D table; an interviewer asking "why descending?" is asking exactly this.

The state that ends, not starts

Longest increasing subsequence breaks the prefix pattern: its sentence — bestEndingAti: the longest strictly increasing subsequence that ends exactly at i — indexes by ending position, because a rising thread can start anywhere. Each cell builds on any earlier smaller value:

for (let i = 1; i < nums.length; i++) {
  for (let j = 0; j < i; j++) {
    if ((nums[j] as number) < (nums[i] as number)) {
      bestEndingAt[i] = Math.max(
        bestEndingAt[i] as number,
        (bestEndingAt[j] as number) + 1
      )
    }
  }
}
return Math.max(...bestEndingAt)

Two consequences, and both are classic interview traps. Strictness: equal values do not chain — [7, 7, 7] has answer 1, and the strict < is the entire enforcement. And the answer is max(...) over the array, not the last cell, because the longest thread rarely ends at the final index — a suffix that only falls leaves every optimum in the middle. When you feel resistance to writing Math.max(...), that resistance is the prefix habit talking; the sentence overrides it.

for (let j = 0; j < i; j++) {
  if ((nums[j] as number)  (nums[i] as number)) {
    bestEndingAt[i] = Math.max(bestEndingAt[i], bestEndingAt[j] + 1)
  }
}

How to debug a grid

Print it, row by row, with row 0 and column 0 visible — a grid printed without its base cases cannot be checked against its own sentence. Then verify one interior cell by hand: pick small i and j, name the three (or two) stories, and compute. A cell that disagrees with your hand has either a wrong formula or a wrong sentence — and the sentence is the likelier culprit, which no amount of loop-staring reveals. For substring-versus-subsequence confusion, run the debugger on abc vs acb: the subsequence answer survives the gap, the substring answer does not, and watching the diagonal skip across it makes the distinction physical. In this concept's practice, the review exercise implements the contiguous run while claiming the subsequence — one noisy week of input and the two answers separate; fail it once on purpose.

Where this bites

• Indexing the table by array positions instead of prefix lengths. A table sized length instead of length + 1 has no home for the empty prefix, and base cases leak into the loop as if (i === 0) branches that multiply. Counter: size for the sentence — prefixes run 0..n — and translate with i - 1 at the array edge, once, visibly.
• Answering from the last cell by reflex. Grid answers usually do live in the corner (edit distance, knapsack); best-ending states (LIS) scatter. Counter: the sentence's last clause says where optima live — quote it in the return statement.
• The wrong sentinel by operator. 0 as "item does not fit" invites max to prefer it; Infinity as "unreachable amount" survives min forever. Counter: the sentinel must be the identity the operator cannot improve, chosen per operator, never by habit.
• Compressing the table before understanding the direction. The 1-D knapsack that walks capacity upward solves the wrong problem correctly — every item, unlimited — and its answers look plausible. Counter: compression is an optimization of a table you can already defend; derive the direction from which cells a take reads, or do not compress.