Designing the state and the transition

Every DP solution is five decisions. Make them explicitly and in order, and the code writes itself.

1. Define the state

Write a sentence: "dp[i] is the …". If you cannot finish the sentence, you do not have a state yet.

• "dp[i] is the length of the longest increasing subsequence ending at index i."
• "dp[i][j] is the minimum edits to turn the first i characters of a into the first j of b."

The words "ending at" versus "up to" matter enormously — they produce different recurrences.

2. Write the transition

How does one state follow from smaller ones? This is the recurrence.

LIS:  dp[i] = 1 + max(dp[j]) for all j < i where a[j] < a[i]
Edit: dp[i][j] = a[i-1] === b[j-1]
                   ? dp[i-1][j-1]
                   : 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

3. Set the base cases

The smallest inputs, answered directly. dp[0][j] = j — turning an empty string into j characters takes j insertions. Most DP bugs are here, not in the transition.

4. Choose the fill order

Every state must be computed after everything it depends on. If the transition reads dp[i-1], iterate i upward. If it reads dp[i+1], iterate downward.

5. Identify the answer

Sometimes dp[n], sometimes the maximum over the whole table. For LIS defined as "ending at i", the answer is max(dp), not dp[n-1] — an easy and costly slip.

Worked example: longest increasing subsequence

function lis(items) {
  if (!items.length) return 0;

  const dp = new Array(items.length).fill(1);   // 3. every element alone is length 1

  for (let i = 1; i < items.length; i++) {      // 4. left to right
    for (let j = 0; j < i; j++) {
      if (items[j] < items[i]) dp[i] = Math.max(dp[i], dp[j] + 1);   // 2.
    }
  }

  return Math.max(...dp);                        // 5.
}

O(n²) time, O(n) space. (There is an O(n log n) version using binary search over a "tails" array — worth knowing exists, and a strong follow-up.)

When you are stuck

Ask: what is the choice at each step? Take it or leave it; split here or not; match these two characters or edit one. The set of choices is the transition, and the parameters those choices depend on are the state.