Dynamic Programming — The 1D Patterns That Cover Most Interviews

DP terrifies candidates because it's taught as magic. It's a checklist. Most interview DP is one-dimensional — an array where dp[i] answers the problem for the first i items.

The 3-question framework

1. State: what does dp[i] mean, in one sentence?
2. Recurrence: how does dp[i] come from earlier entries?
3. Base case: what are dp[0] (and dp[1])?

If you can fill those three lines, the code writes itself.

Worked trio — same skeleton, three classics

// 1. CLIMBING STAIRS — "how many ways"
// dp[i] = ways to reach step i = dp[i-1] + dp[i-2]
let a = 1, b = 1;
for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
return b;

// 2. HOUSE ROBBER — "max value, can't take adjacent"
// dp[i] = max(dp[i-1],            // skip house i
//             dp[i-2] + nums[i])  // rob house i
let skip = 0, rob = 0;
for (const x of nums) [skip, rob] = [Math.max(skip, rob), skip + x];
return Math.max(skip, rob);

// 3. COIN CHANGE — "min coins to make amount"
// dp[a] = 1 + min(dp[a - coin]) over all coins
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let a = 1; a <= amount; a++)
  for (const c of coins)
    if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
return dp[amount] === Infinity ? -1 : dp[amount];

Spot DP when…

• The ask is count ways / min cost / max value (not "list all" — that's backtracking).
• Decisions now constrain decisions later (rob a house → can't rob the next).
• Your recursive brute force recomputes identical subproblems — memoise it, and that IS DP (top-down).

Top-down vs bottom-up

Memoisation = recursion + cache (easier to derive). Tabulation = fill the array forward (faster, no stack limits). Interviews accept either; derive top-down, convert if asked.

Practice now

• Climbing Stairs
• Coin Change — with a hidden large-amount test that kills naive recursion
• Fibonacci — the warm-up that times out exponential solutions on purpose