The Recurrence First

Every dynamic programming question is answered before the first line of code, in one sentence: what exactly does a cell of my table mean? "The best at position i" is not an answer — best ending at i, best through i, best using the first i items? The sentence chooses the recurrence, the recurrence chooses the loop, and a wrong DP is almost always a wrong sentence that was implemented faithfully.

The sentence, the house, and the recurrence

House robber, stated as a sentence: the best loot obtainable from the first i houses, where taking house i forbids house i − 1. That sentence forces two running values, because "best through i" depends on "best through i − 2":

export function rob(houses: number[]): number {
  let previous = 0 // best that stops at the last house seen
  let beforePrevious = 0 // best that stops one before that

  for (const loot of houses) {
    const current = Math.max(previous, beforePrevious + loot)
    beforePrevious = previous
    previous = current
  }
  return previous
}

Notice what is not here: no array, no memo, no recursion. A DP whose table row depends only on the previous row is two variables. People write a full table, then "optimize" it later; writing the sentence first skips the ceremony. When the state genuinely needs more history — longest common subsequence needs a 2-D table because its sentence mentions prefixes of two strings — the table reappears, and it is welcome.

Memoization is the sentence, verbatim, plus a cache

Counting staircases with steps of 1 or 2 is fibonacci in costume. The recursive sentence — ways(k) = ways(k − 1) + ways(k − 2) — compiles straight into code, and the cache turns its exponential re-derivation into linear:

export function countPaths(steps: number): number {
  const memo = new Map<number, number>()

  function climb(remaining: number): number {
    if (remaining <= 1) return 1
    const cached = memo.get(remaining)
    if (cached !== undefined) return cached

    const paths = climb(remaining - 1) + climb(remaining - 2)
    memo.set(remaining, paths)
    return paths
  }

  return climb(steps)
}

Look before compute, store after — the same ordering discipline as the hash-map chapter, for the same reason: the cache holds settled answers, and an answer is not settled until it is computed. The cache key is the argument list: one number here, an index pair for edit distance, "index + remaining capacity" for knapsack. If you cannot name the key, the sentence is not finished.

function climb(remaining: number): number {
  if (remaining <= 1) return 1
  const cached = memo.(remaining)
  if (cached !== undefined) return cached
  const paths = climb(remaining - 1) + climb(remaining - 2)
  memo.set(remaining, paths)
  return paths
}

Greedy is the enemy that looks like a friend

Coins of 1, 3 and 4, target 6. Greedy takes the biggest that fits — 4 + 1 + 1, three coins. The optimum is 3 + 3, two. Greedy fails when a locally worse choice is globally necessary, and coin systems are the standard witness: no ordering of the local choice repairs it, because the problem is the strategy, not the ordering. The DP for fewest coins asks, for every amount below the target, "what does each coin offer?" — every offer is considered, so no globally-necessary choice is filtered early:

for (let k = 1; k <= amount; k++) {
  for (const coin of coins) {
    if (coin <= k) {
      best[k] = Math.min(best[k], (best[k - coin] as number) + 1)
    }
  }
}

The unreachable amount is represented as infinity — the sentinel that survives every min unless a real path replaces it. Returning -1 is then a one-line Number.isFinite check, and "impossible" never contaminates arithmetic on the way there.

if (coin <= k) {
  best[k] = Math.(best[k], (best[k - coin] as number) + 1)
}

How to debug a DP

Print the whole table after it is built, and read it against the sentence. A longest-increasing-subsequence table whose rows say "longest run seen so far" instead of "longest ending here" implements a different sentence than the one in your head — that gap is the bug, and no amount of loop-staring finds it, because every line is faithful to some sentence. For 2-D tables, print row by row and check one row by hand before trusting the rest. For memoized recursion, print the key on entry and exit — a cache hit on a key never computed is a key-collision, and a full re-derivation of the same key late in the run is a missing cache write. In the exercises for this concept, the greedy-vs-DP review is the one to fail on purpose once: its hidden tests are exactly the coin systems where greedy quietly settles for more.

Where this bites

• A fuzzy cell meaning. "Best so far" tables answer neither best-ending nor best-through and fail on inputs that distinguish them — typically the answer should be max(...table), not table[n − 1]. Counter: write the sentence as a comment above the table and make every line of code refer to it.
• Answering from the last cell by reflex. The longest increasing subsequence can end anywhere, so the answer is the maximum over the array; reading the last cell reports a number that is merely plausible. Counter: the sentence says where optima live — leaves, any cell, or a corner — and the return statement must quote it.
• Greedy where only exhaustive works. Coin systems, task intervals with overlaps — any input where skipping a locally-bad option deletes the global optimum. Counter: try to construct one input where every greedy choice is locally right and globally wrong; if you can, that construction is the DP's recurrence.
• Impossible states as zero. Using 0 for unreachable makes every min/max prefer it or discard it wrongly — impossible must be the identity the operation cannot improve, which is infinity for min and minus infinity for max. Counter: pick sentinels by operator, not by habit.