The classic DP families

Learn these six and you will recognise most of what you are asked.

1. 0/1 knapsack — take it or leave it

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);   // dp[c] = best value at capacity c

  for (let i = 0; i < weights.length; i++) {
    // Descending: each item may be used once, so do not reuse this row's updates.
    for (let c = capacity; c >= weights[i]; c--) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

The loop direction is the whole distinction: descending gives 0/1, ascending gives unbounded (each item reusable). Subset sum, partition into equal halves, and "target sum" are all this recurrence.

2. Coin change — unbounded knapsack

Minimum coins to reach an amount: ascending inner loop, Math.min instead of Math.max. Counting the number of ways swaps the min for a sum — and the loop nesting decides whether combinations or permutations are counted.

3. Longest common subsequence — two sequences

dp[i][j] over prefixes of both strings. Characters match: extend the diagonal. They do not: take the better of dropping one from either side. Edit distance, diff tools and DNA alignment are the same table.

4. Longest increasing subsequence — one sequence

The lesson before this one. Also the core of "russian doll envelopes" and "maximum length chain of pairs" after a sort.

5. Grid paths — two dimensions

// Minimum path sum: each cell takes the cheaper of the two ways in.
dp[r][c] = grid[r][c] + Math.min(dp[r - 1][c], dp[r][c - 1]);

Unique paths, minimum path sum, maximal square, and dungeon-game variants all fill a grid this way.

6. Interval DP — solve inside out

dp[i][j] over a range, filled by increasing length. Matrix chain multiplication, burst balloons, longest palindromic subsequence. The outer loop is the length, not the index — that inversion is what makes it feel unfamiliar.

The table to keep

Recognition is most of the battle. If a new problem resembles one of these six, start from its recurrence and adjust rather than deriving from nothing.