DSA & System Design
Pattern 20 of 24 · Search & optimisation · 40 min

Dynamic Programming I: 1D

Define what dp[i] means, write how it depends on smaller i, and fill a table instead of recomputing overlapping subproblems.

Spot it:number of waysminimum / maximum costcan it be done?choices at each step overlapJavaScript you'll use: Recursion, the call stack and memoization Arrays: create, read, update Map and Set
Say it in 30 seconds
  • O(2^n) to O(n)Two-branch recursion against a memo or table
  • O(A × k)Over an amount A with k choices
  • O(n²)Ending at i, scanning every earlier j
Show what to say

“When a problem asks for the number of ways or a minimum or maximum over choices, and my brute-force recursion repeats the same arguments, I use DP. I define dp[i] in words, write the recurrence from the last decision, set the base cases and fill in order. Exponential becomes O(states × choices), and rolling variables often give O(1) space.”

Trade-offs

  • Top-down vs bottom-up: top-down is the brute force plus a memo and suits few reachable states; bottom-up has no stack limit and allows O(1) space.
  • DP vs greedy: coins 1, 3, 4 for amount 6 break greedy; a counterexample means DP, a proven exchange argument means greedy.
  • Table vs rolling variables: if dp[i] reads only the last one or two cells, two variables give O(1) space; otherwise keep the array.

Bring it up before they ask

Say what dp[i] means in words first, size the table n + 1 when the top is index n, and test a memo with has(), not a truthy get(), because a cached 0 is a real answer.

0 of 0 sections ticked
30-second answer

Dynamic programming is recursion that never solves the same question twice. Write each answer down once, build it from smaller answers, and a slow brute force becomes a quick loop.

When to reach for it

Listing every solution is Backtracking. DP is for when Greedy has a counterexample.

Spot it in the problem0 of 4

Tap the signals you can see in the problem.

Rememberthe number of waysminimum or maximumis it possible?same arguments

Pick your variant
  • Fixed look-back

    dp[i] meansanswer for step i

    Climbing Stairs
  • Ending at i

    dp[i] meansbest answer ending at nums[i]

    Longest Increasing Subsequence
  • Over an amount

    dp[i] meansanswer for total a

    Coin Change
  • Prefix with a cut

    dp[i] meansanswer for s.slice(0, i)

    Word Break

The core idea: solve each subproblem once

Picture a staircase with a toll on each step.

Read more · 123 words

You climb one or two steps at a time and want the cheapest way to the top. Ask only about the last move: you reached step i from i - 1 or from i - 2. So the cheapest way to i is the cheaper of those two.

Correct, but slow: every call makes two more, repeating the same questions. There are only n + 1 different ones. So write each answer on a sticky note (a memo) and look it up next time. Compare both presets, then try your own costs with Edit input:

Two things make a problem fit:

  • Repeated questions: the same small question keeps coming back.
  • Built from smaller answers: the best answer for i comes from best answers for smaller indices.
best(i) = Math.min(best(i - 1) + cost[i - 1], best(i - 2) + cost[i - 2]);   // best(0) = best(1) = 0

Plain recursion vs memoized recursion: the call tree

calls of best(i)
5▲ now
i
5
calls
1

best(5) asks for the cheapest way to stand on the top, step 5, with cost = [1, 4, 2, 3, 1]. The last move came from step 4 or step 3, so ask for both.

function best(i) {
  if (i <= 1) return 0;
  return Math.min(best(i - 1) + cost[i - 1],
                  best(i - 2) + cost[i - 2]);
}

function bestMemo(i, memo) {
  if (i <= 1) return 0;
  if (memo.has(i)) return memo.get(i);
  const value = Math.min(bestMemo(i - 1, memo) + cost[i - 1],
                         bestMemo(i - 2, memo) + cost[i - 2]);
  memo.set(i, value);
  return value;
}
All steps as text
  1. best(5) asks for the cheapest way to stand on the top, step 5, with cost = [1, 4, 2, 3, 1]. The last move came from step 4 or step 3, so ask for both.
  2. best(4): the last move onto step 4 came from step 3 or from step 2, so ask for both.
  3. best(3): the last move onto step 3 came from step 2 or from step 1, so ask for both.
  4. best(2): the last move onto step 2 came from step 1 or from step 0, so ask for both.
  5. best(1) is a base case: you may start on step 1 for free, so it costs 0.
  6. best(0) is a base case: you may start on step 0 for free, so it costs 0.
  7. best(2) = min(0 + 4, 0 + 1) = 1.
  8. best(1) is a base case: you may start on step 1 for free, so it costs 0.
  9. best(3) = min(1 + 2, 0 + 4) = 3.
  10. best(2) again! It was already solved further left, but plain recursion has no memory, so its whole subtree is rebuilt from scratch.
  11. best(1) is a base case: you may start on step 1 for free, so it costs 0. This call is still wasted work: it only happens because a repeated subtree is being rebuilt.
  12. best(0) is a base case: you may start on step 0 for free, so it costs 0. This call is still wasted work: it only happens because a repeated subtree is being rebuilt.
  13. best(2) = min(0 + 4, 0 + 1) = 1.
  14. best(4) = min(3 + 3, 1 + 2) = 3.
  15. best(3) again! It was already solved further left, but plain recursion has no memory, so its whole subtree is rebuilt from scratch.
  16. best(2) again! It was already solved further left, but plain recursion has no memory, so its whole subtree is rebuilt from scratch.
  17. best(1) is a base case: you may start on step 1 for free, so it costs 0. This call is still wasted work: it only happens because a repeated subtree is being rebuilt.
  18. best(0) is a base case: you may start on step 0 for free, so it costs 0. This call is still wasted work: it only happens because a repeated subtree is being rebuilt.
  19. best(2) = min(0 + 4, 0 + 1) = 1.
  20. best(1) is a base case: you may start on step 1 for free, so it costs 0. This call is still wasted work: it only happens because a repeated subtree is being rebuilt.
  21. best(3) = min(1 + 2, 0 + 4) = 3.
  22. best(5) = min(3 + 1, 3 + 3) = 4. That took 15 calls for only 6 different subproblems: the 8 calls marked ✕ recomputed answers that were already known. One more step in the staircase roughly doubles this.

Step by step: the DP recipe

Six questions, in order, turn a brute force into a DP.

Read more · 145 words

  1. Define the state in words

    "dp[i] = the cheapest cost to stand on step i." Vague here means wrong later.

  2. Write the recurrence from the last decision

    The last move came from i - 1 or i - 2. Combine with min, max, + (counting) or || (feasibility).

  3. Pin down the base cases

    Here dp[0] = dp[1] = 0. When counting, doing nothing is one way (dp[0] = 1).

  4. Choose the evaluation order

    Fill each cell after the cells it reads: loop i upward.

  5. Read the answer cell

    dp[n], dp[amount], or the best over all cells.

  6. Optimise the space

    If dp[i] reads only the last one or two cells, keep two variables.

Play with it

Rob houses for the most loot without hitting two neighbours. Each cell picks rob (loot[i] + dp[i - 2]) or skip (dp[i - 1]). Plan your own haul, then press Run.

Interactive

House robber lab

Never rob two neighbours. Pick your haul, then let the DP find the best one.

27931854dp[−2]0dp[−1]0dp[0]dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]dp[7]before the street
Cells 0/8Recursion 109 callsSubsets 256Your haul 0 (pick houses)

8 houses. Tap houses to rob them yourself (no two neighbours), then press Run or Step to let the DP fill the row.

Your street

Templates

Template 1: fixed look-back, four ways

Same answers, four costs. Write the plain recursion first. The memo, table and rolling variables are mechanical rewrites.

Bottom-up fills dp from the base cases upward, so the cells each step reads are ready:

This is Climbing StairsEasy and House RobberMedium.

// Form 1: plain recursion, straight from the recurrence. Correct, but best(i - 1) and best(i - 2) both
// re-solve the same smaller steps, so the call tree roughly doubles per step: O(2^n). Fine for n = 20, hopeless for 50.
export function minCostRecursive(cost) {
  const best = (i) => {
    if (i <= 1) return 0; // you may start on step 0 or 1 for free
    return Math.min(best(i - 1) + cost[i - 1], best(i - 2) + cost[i - 2]);
  };
  return best(cost.length); // the top is one past the last step
}

Bottom-up: fill dp[] from the base cases up

cost (paid when you leave a step) (7)
1
4
2
3
1
5
2
dp (cheapest cost to stand on step i) (8)
n
7

State in words: dp[i] = the cheapest total cost to stand on step i. The top is step 7, one past the last step, so dp needs 8 cells.

function minCost(cost) {
  const n = cost.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 0; dp[1] = 0;     // start on 0 or 1 free
  for (let i = 2; i <= n; i++) {
    const oneStep = dp[i - 1] + cost[i - 1];
    const twoStep = dp[i - 2] + cost[i - 2];
    dp[i] = Math.min(oneStep, twoStep);
  }
  return dp[n];
}
All steps as text
  1. State in words: dp[i] = the cheapest total cost to stand on step i. The top is step 7, one past the last step, so dp needs 8 cells.
  2. Base cases: you may start on step 0 or step 1 without paying, so dp[0] = 0 and dp[1] = 0. The recurrence can't build these: they have no two earlier steps.
  3. To stand on step 2, the last move came from step 1 (dp[1] + cost[1] = 0 + 4 = 4) or from step 0 (dp[0] + cost[0] = 0 + 1 = 1). Both cells are already filled.
  4. dp[2] = min(4, 1) = 1, coming from step 0. Every later cell reads this number instead of recomputing it.
  5. To stand on step 3, the last move came from step 2 (dp[2] + cost[2] = 1 + 2 = 3) or from step 1 (dp[1] + cost[1] = 0 + 4 = 4). Both cells are already filled.
  6. dp[3] = min(3, 4) = 3, coming from step 2. Every later cell reads this number instead of recomputing it.
  7. To stand on step 4, the last move came from step 3 (dp[3] + cost[3] = 3 + 3 = 6) or from step 2 (dp[2] + cost[2] = 1 + 2 = 3). Both cells are already filled.
  8. dp[4] = min(6, 3) = 3, coming from step 2. Every later cell reads this number instead of recomputing it.
  9. To stand on step 5, the last move came from step 4 (dp[4] + cost[4] = 3 + 1 = 4) or from step 3 (dp[3] + cost[3] = 3 + 3 = 6). Both cells are already filled.
  10. dp[5] = min(4, 6) = 4, coming from step 4. Every later cell reads this number instead of recomputing it.
  11. To stand on step 6, the last move came from step 5 (dp[5] + cost[5] = 4 + 5 = 9) or from step 4 (dp[4] + cost[4] = 3 + 1 = 4). Both cells are already filled.
  12. dp[6] = min(9, 4) = 4, coming from step 4. Every later cell reads this number instead of recomputing it.
  13. To stand on step 7, the last move came from step 6 (dp[6] + cost[6] = 4 + 2 = 6) or from step 5 (dp[5] + cost[5] = 4 + 5 = 9). Both cells are already filled.
  14. dp[7] = min(6, 9) = 6, coming from step 6. Every later cell reads this number instead of recomputing it.
  15. The answer cell is dp[7] = 6. Following the "came from" choices back from the top gives the path: pay on steps 0, 2, 4, 6. Each cell only read the two before it, so two variables would be enough (O(1) space).

Template 2: DP over an amount

A target number and reusable pieces?

Read more · 52 words

Index the table by amount. dp[a] tries every last piece and reads the cell for what is left. Here, the fewest perfect squares that sum to n:

Swap squares for coins and you have Coin ChangeMedium. Swap min for + with dp[0] = 1 to count ordered ways. Unordered ways need 2D DP.

DP over an amount: fewest perfect squares

dp (fewest squares that sum to a) (13)
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
n
12

State in words: dp[a] = the fewest perfect squares that add up to a. Every cell starts at ∞, which means "not solved yet".

function numSquares(n) {
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= n; a++) {
    for (let k = 1; k * k <= a; k++) {
      dp[a] = Math.min(dp[a], dp[a - k * k] + 1);
    }
  }
  return dp[n];
}
All steps as text
  1. State in words: dp[a] = the fewest perfect squares that add up to a. Every cell starts at ∞, which means "not solved yet".
  2. Base case: the amount 0 needs no squares at all, so dp[0] = 0. Every other amount is built on top of it.
  3. dp[1]: try each square that fits as the last piece. 1 leaves 0: dp[0] + 1 = 1. The fewest is 1.
  4. dp[2]: try each square that fits as the last piece. 1 leaves 1: dp[1] + 1 = 2. The fewest is 2.
  5. dp[3]: try each square that fits as the last piece. 1 leaves 2: dp[2] + 1 = 3. The fewest is 3.
  6. dp[4]: try each square that fits as the last piece. 1 leaves 3: dp[3] + 1 = 4; 4 leaves 0: dp[0] + 1 = 1. The fewest is 1.
  7. dp[5]: try each square that fits as the last piece. 1 leaves 4: dp[4] + 1 = 2; 4 leaves 1: dp[1] + 1 = 2. The fewest is 2.
  8. dp[6]: try each square that fits as the last piece. 1 leaves 5: dp[5] + 1 = 3; 4 leaves 2: dp[2] + 1 = 3. The fewest is 3.
  9. dp[7]: try each square that fits as the last piece. 1 leaves 6: dp[6] + 1 = 4; 4 leaves 3: dp[3] + 1 = 4. The fewest is 4.
  10. dp[8]: try each square that fits as the last piece. 1 leaves 7: dp[7] + 1 = 5; 4 leaves 4: dp[4] + 1 = 2. The fewest is 2.
  11. dp[9]: try each square that fits as the last piece. 1 leaves 8: dp[8] + 1 = 3; 4 leaves 5: dp[5] + 1 = 3; 9 leaves 0: dp[0] + 1 = 1. The fewest is 1.
  12. dp[10]: try each square that fits as the last piece. 1 leaves 9: dp[9] + 1 = 2; 4 leaves 6: dp[6] + 1 = 4; 9 leaves 1: dp[1] + 1 = 2. The fewest is 2.
  13. dp[11]: try each square that fits as the last piece. 1 leaves 10: dp[10] + 1 = 3; 4 leaves 7: dp[7] + 1 = 5; 9 leaves 2: dp[2] + 1 = 3. The fewest is 3.
  14. dp[12]: try each square that fits as the last piece. 1 leaves 11: dp[11] + 1 = 4; 4 leaves 8: dp[8] + 1 = 3; 9 leaves 3: dp[3] + 1 = 4. The fewest is 3.
  15. Walking the chosen squares back from dp[12] gives 4 + 4 + 4, so the answer is 3. Grabbing the biggest square first would need 4 (9 + 1 + 1 + 1): greedy fails here, the table doesn't.
// DP over an amount: dp[a] = the fewest perfect squares that add up to a.
// Each cell tries every possible LAST piece (a square k² that fits) and reads the cell for what is left.
// Swap the squares for a coin list and this is Coin Change; keep Infinity for amounts that can't be made.
export function numSquares(n) {
  const dp = new Array(n + 1).fill(Infinity); // Infinity = "not reachable (yet)"
  dp[0] = 0;                                   // the amount 0 needs no pieces
  for (let a = 1; a <= n; a++) {
    for (let k = 1; k * k <= a; k++) {
      dp[a] = Math.min(dp[a], dp[a - k * k] + 1);
    }
  }
  return dp[n];
}

Template 3: ending at i, looking back at every earlier j

For "best subsequence" problems, let dp[i] be the best answer ending at nums[i]: scan every earlier j and extend the best.

Read more · 50 words

That is O(n²), and the answer is the best cell.

Add 1 instead of nums[i] for Longest Increasing SubsequenceMedium. Maximum SubarrayMedium only looks at i - 1: dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]). Word BreakMedium asks: is some cut j true, with s.slice(j, i) a word?

// "Ending at i": dp[i] = the best answer whose LAST element is nums[i].
// dp[i] looks back at every j < i that may come right before i, so it costs O(n²).
// The answer can end anywhere, so it is the best cell, not dp[n - 1].
// Here: the largest sum of a strictly increasing subsequence.
export function maxSumIncreasing(nums) {
  if (nums.length === 0) return 0;
  const dp = nums.slice(); // nums[i] on its own is already a valid subsequence ending at i
  let best = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + nums[i]); // extend the best chain ending at j
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}

Try it

try-it.js
// The same problem four ways. Edit cost and press Run: all four must agree.
const cost = [1, 4, 2, 3, 1, 5, 2];
console.log(minCostRecursive(cost), minCostMemo(cost), minCostTable(cost), minCostRolling(cost)); // 6 6 6 6

// Why the memo matters: count the calls each version makes on a 25-step staircase.
const long = Array.from({ length: 25 }, (_, i) => (i * 7) % 10);
let plainCalls = 0;
const plain = (i) => {
  plainCalls++;
  return i <= 1 ? 0 : Math.min(plain(i - 1) + long[i - 1], plain(i - 2) + long[i - 2]);
};
let memoCalls = 0;
const memo = new Map();
const cached = (i) => {
  memoCalls++;
  if (i <= 1) return 0;
  if (!memo.has(i)) memo.set(i, Math.min(cached(i - 1) + long[i - 1], cached(i - 2) + long[i - 2]));
  return memo.get(i);
};
console.log(plain(25), `${plainCalls} calls`);  // 41 242785 calls
console.log(cached(25), `${memoCalls} calls`);  // 41 49 calls

// DP over an amount: the fewest perfect squares that add up to n.
console.log(numSquares(12), numSquares(13));    // 3 2

Complexity

Time is states × work per state.

Read more · 32 words
FormTimeSpace
Plain recursionO(2^n)O(n)
Memo or tableO(n)O(n)
Rolling variablesO(n)O(1)
Ending at i, every jO(n²)O(n)

JavaScript you'll use

JavaScript refresher: Recursion, the call stack and memoization Arrays: create, read, update Map and Set
Read more · 48 words

The memo trap: if (memo.get(i)) treats a cached 0 as missing, so test memo.has(i). Memoized recursion on n = 10^5 overflows the stack: go bottom-up.

const dp = new Array(n + 1).fill(0);           // one cell per state, n + 1 when the top is index n
const best = new Array(amount + 1).fill(Infinity);
best[0] = 0;                                   // Infinity = "can't be made", min() ignores it
const memo = new Map();                        // if (memo.has(key)) return memo.get(key);
[twoBack, oneBack] = [oneBack, current];       // roll two variables forward
return best[amount] === Infinity ? -1 : best[amount];

Interview questions

Top-down or bottom-up: which should I write in an interview?

Top-down when the recurrence is the hard part: it is the brute force plus a two-line memo. Bottom-up for large inputs or O(1) space.

How do you know it's DP and not greedy?

Try to break greedy on a small case: coins 1, 3, 4 for amount 6. Greedy gives 4 + 1 + 1, but 3 + 3 is better. A counterexample means DP.

The interviewer wants the actual choices, not just the value. What changes?

Keep the full table. Walk back from the answer cell, asking which option produced each cell.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. Plain recursion for min-cost stairs makes about 2^n calls, but the memoized version makes about 2n. Where does the saving come from?

Practice problems

Solve these in the browser editor. Each runs against hidden tests; the step-by-step solution unlocks after a wrong submission.

Open these in the problem list →

In real systems

This pattern is not only for coding rounds. Here is where it does the work in a design interview.

Next: Two inputs or a grid make the table two-dimensional.