Dynamic programming: 1D

The problem DP exists to fix, drawn out

Plain recursion on overlapping subproblems redoes the same work exponentially many times. Watch fib(5) expand:

DP is exactly one idea: cache the result of each distinct subproblem the first time you compute it, and look it up instead of recomputing it every other time. That's it — the rest is just two different ways of organizing that cache.

Top-down (memoization) — recursion, plus a cache

function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n); // seen this exact input before — reuse it

  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}

This turns the tree above from O(2ⁿ) into O(n) — there are only n distinct subproblems (fib(0) through fib(n)), and each one is now computed exactly once.

Bottom-up (tabulation) — build the table forward, no recursion at all

function fibBottomUp(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

// space-optimized: fib only ever needs the last 2 values — O(1) space
function fibOptimized(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }
  return prev1;
}

The general recipe — the four questions every 1D DP answers

1. What does dp[i] mean? — state it in one sentence before writing any code. ("dp[i] = the max sum of a subarray ending exactly at i.")
2. What's the recurrence? — how does dp[i] relate to earlier states?
3. What's the base case? — the smallest i you can answer directly.
4. What order do you fill it in? — usually left to right, since dp[i] needs earlier values.

Climbing Stairs and Min Cost Climbing Stairs

You climb a staircase of n steps, taking 1 or 2 steps at a time. In how many different sequences of moves do you reach the top? Start from the last move. To stand on step i you came from step i - 1 (with a 1-step) or from step i - 2 (with a 2-step), and those are the only two ways. So ways[i] = ways[i - 1] + ways[i - 2], with ways[1] = 1 and ways[2] = 2. This is the Fibonacci recurrence from the start of the chapter wearing a costume, and it has the same O(n) time with O(1) space once you keep only the last two values.

The version with a price is where the four questions earn their keep. Each step i has a cost cost[i] that you pay when you leave it, you may start on step 0 or step 1, and the top is one past the last index. State it in one sentence first: best[i] is the cheapest total to be standing on step i, where step n is the top. Then best[0] = best[1] = 0 (you start there for free) and each later step is reached from one of the two steps below by paying for the step you leave.

function climbStairs(n) {
  if (n <= 2) return n;
  let twoBack = 1, oneBack = 2; // ways to reach step 1 and step 2
  for (let step = 3; step <= n; step++) {
    [twoBack, oneBack] = [oneBack, oneBack + twoBack]; // last move was a 1-step or a 2-step
  }
  return oneBack;
}

function minCostClimbingStairs(cost) {
  const n = cost.length;
  const best = new Array(n + 1).fill(0); // best[i] = cheapest way to STAND on step i; the top is step n
  for (let i = 2; i <= n; i++) {
    best[i] = Math.min(best[i - 1] + cost[i - 1], best[i - 2] + cost[i - 2]); // pay for the step you leave
  }
  return best[n];
}

Dry run: minCostClimbingStairs([10, 15, 20])

The answer is 15: start on step 1, pay 15, jump over step 2 to the top. Both functions are O(n) time, and the second one can be reduced to O(1) space the same way as Fibonacci.

Worked example: House Robber

Can't rob two adjacent houses. At each house, you either skip it (carry forward the best so far) or rob it (best from two houses back, plus this house's value).

function rob(nums) {
  let prevSkip = 0, prevTake = 0; // best up to i-2, best up to i-1
  for (const val of nums) {
    const curr = Math.max(prevTake, prevSkip + val); // skip this OR rob this
    prevSkip = prevTake;
    prevTake = curr;
  }
  return prevTake;
}

Notice the state definition again: "best total up to and including house i." Once that's pinned down precisely, the recurrence (dp[i] = max(dp[i-1], dp[i-2] + nums[i])) falls out directly from re-reading the problem statement.

House Robber II — a circle is two lines

Now the houses stand in a circle, so the first and the last are neighbours and cannot both be robbed. Do not invent a new recurrence. Ask which of the two houses is not robbed. Either the last house is left alone, and the houses 0..n - 2 form an ordinary line, or the first house is left alone, and 1..n - 1 form one. Any valid plan belongs to at least one of the two cases, and each case is the problem you already solved, so the answer is the larger of the two.

function robLine(nums, lo, hi) { // best total from nums[lo..hi], no two adjacent
  let skip = 0, take = 0;
  for (let i = lo; i <= hi; i++) {
    [skip, take] = [take, Math.max(take, skip + nums[i])];
  }
  return take;
}

function robCircle(nums) {
  const n = nums.length;
  if (n === 1) return nums[0]; // the two ranges below would both be empty
  return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1)); // skip the last, or skip the first
}

For [2, 3, 2] the first line [2, 3] gives 3, the second line [3, 2] gives 3, and the answer is 3. Robbing both 2s would give 4 on a line, which a circle forbids. For [1, 2, 3, 1] the lines [1, 2, 3] and [2, 3, 1] give 4 and 3, so the answer is 4. Time is O(n) with O(1) space: two passes over the array.

This move, "break the circle by deciding one element's fate", is a reusable idea: circular arrays turn into two linear problems in many places, not only here.

Decode Ways — counting with two look-backs

The letters A to Z are encoded as 1 to 26. A string of digits can be read in several ways: "226" can be 2-2-6 (BBF), 22-6 (VF) or 2-26 (BZ). Count the readings. Define ways[i] as the number of ways to decode the first i characters. The last letter of any reading uses either the last one character or the last two, so there are exactly two cases to add:

• The last character alone is a letter if it is 1 to 9, and then it adds ways[i - 1]. A 0 cannot stand alone and adds nothing.
• The last two characters together are a letter if they read 10 to 26, and then they add ways[i - 2].

The empty prefix has one way (read nothing), so ways[0] = 1, and the first character gives 1 if it is not "0" and 0 otherwise.

function numDecodings(s) {
  const n = s.length;
  if (n === 0) return 0;
  let twoBack = 1; // ways to decode the first i - 2 characters (the empty prefix has 1 way)
  let oneBack = s[0] === "0" ? 0 : 1; // ways to decode the first i - 1 characters
  for (let i = 2; i <= n; i++) {
    let ways = 0;
    if (s[i - 1] !== "0") ways += oneBack; // the last character alone: 1..9
    const pair = Number(s.slice(i - 2, i));
    if (pair >= 10 && pair <= 26) ways += twoBack; // the last two together: 10..26
    twoBack = oneBack;
    oneBack = ways;
  }
  return oneBack;
}

Dry run: "226" and "206"

"206" has exactly one reading, 20-6. The two-value window keeps the space at O(1), and the time is O(n).

Word Break — does a prefix split into words?

Given a string s and a dictionary, can s be cut into a sequence of dictionary words? Define ok[i] as whether the first i characters can be split. The last word in any split is some s[j..i - 1], and what is in front of it must itself be a splittable prefix. So ok[i] is true when some j has ok[j] true and s[j..i - 1] in the dictionary. The empty prefix is splittable: ok[0] = true.

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const maxLen = Math.max(0, ...wordDict.map((w) => w.length));
  const ok = new Array(s.length + 1).fill(false); // ok[i] = the first i characters can be split into words
  ok[0] = true; // the empty prefix needs no words

  for (let i = 1; i <= s.length; i++) {
    for (let j = Math.max(0, i - maxLen); j < i; j++) { // the last word is s[j..i-1], at most maxLen long
      if (ok[j] && words.has(s.slice(j, i))) {
        ok[i] = true;
        break;
      }
    }
  }
  return ok[s.length];
}

Dry run: s = "leetcode", dictionary ["leet", "code"]

The inner loop only looks back maxLen characters, because no word is longer than that. With L the length of the longest word, the loops make O(n · L) substring checks, and each check builds a string of up to L characters and hashes it, so the time is O(n · L²). Space is O(n) plus the dictionary. Without the bound the same code is O(n³) in the worst case.

Worked example: Longest Increasing Subsequence

// O(n²) — dp[i] = length of the longest increasing subsequence ENDING at i
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  const dp = new Array(nums.length).fill(1); // every element alone is a subsequence of length 1
  let best = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return best;
}

There's an O(n log n) version worth knowing exists, even if the O(n²) is your first answer: maintain an array tails where tails[k] is the smallest possible "tail value" of an increasing subsequence of length k+1, and binary search (from the earlier chapter) for where each new number belongs. The length of tails at the end is the answer — a nice example of two earlier patterns (DP + binary search) combining.

LIS in O(n log n) — the tails array

The O(n²) table asks, for every i, a question about every j < i. The faster version flips the bookkeeping. Keep tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1 among the elements seen so far. Why the smallest? Because for extending, a smaller tail is never worse: anything that can follow a tail of 7 can follow a tail of 3.

Two facts make it work. First, tails is always strictly increasing: if a subsequence of length 3 ends at 5, then one of length 2 ends at something smaller than 5, namely its own second-to-last value. Because it is sorted, a binary search can place each new number. Second, a new number x does one of two things. If it is larger than every tail, it extends the longest run and is appended. Otherwise it replaces the first tail that is greater than or equal to it, which lowers that length's best tail without changing any length.

function lengthOfLISFast(nums) {
  const tails = []; // tails[k] = smallest tail of any increasing subsequence of length k + 1
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) { // first index whose tail is >= x
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // extend the longest run, or lower an existing tail
  }
  return tails.length;
}

Dry run: [10, 9, 2, 5, 3, 7, 101, 18]

The answer is the final length, 4. Time is O(n log n), one binary search per element, and space is O(n).

Two meanings of dp[i], and Kadane's two states

Look at the state definitions used so far, because they come in two flavours, and mixing them up is the commonest reason a recurrence will not close.

A "first i items" cell is a complete answer about that whole prefix, so the last cell already answers the whole question. An "ending at i" cell is forced to include item i, so the best solution can end anywhere and you must scan every cell.

Maximum Subarray (Kadane's algorithm) is the cleanest example of the second flavour. Let endingHere be the best sum of a non-empty subarray that ends at i. That subarray either is just nums[i] or extends the best subarray that ended at i - 1, so endingHere = max(nums[i], endingHere + nums[i]), and the answer is the largest endingHere seen. For [1, -3, 4, -1, 2, 1, -5, 4] the running values of endingHere are 1, -2, 4, 3, 5, 6, 1, 5, and the best is 6 from [4, -1, 2, 1].

Maximum Product Subarray looks the same and is not, because a negative number turns the smallest product into the largest. One state is therefore not enough. Keep both the largest and the smallest product of a subarray ending at i, and at each step take the best and worst of three candidates: start fresh at x, extend the maximum, or extend the minimum.

function maxSubArray(nums) {
  let endingHere = nums[0], best = nums[0]; // endingHere = best sum of a subarray ending at i
  for (let i = 1; i < nums.length; i++) {
    endingHere = Math.max(nums[i], endingHere + nums[i]); // extend the previous run, or start fresh
    best = Math.max(best, endingHere);
  }
  return best;
}

function maxProduct(nums) {
  let hi = nums[0], lo = nums[0], best = nums[0]; // largest and smallest product ending at i
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    const candidates = [x, hi * x, lo * x]; // start fresh, extend the max, extend the min
    hi = Math.max(...candidates);
    lo = Math.min(...candidates);
    best = Math.max(best, hi);
  }
  return best;
}

Dry run: maxProduct([-2, 3, -4])

The 24 comes from lo · x, the earlier minimum times a negative: without the second state the answer would be 3. Both functions are O(n) time and O(1) space. A zero is handled by the "start fresh" candidate, which resets both values.

Worked example: Coin Change — minimum coins to make an amount

Given coin denominations and a target amount, find the fewest coins that sum to it (or report it's impossible). This is the DP counterpart to the greedy "make change" instinct — and greedy provably fails here for arbitrary denominations (try amount 6 with coins [1, 3, 4]: greedy picks 4+1+1 = 3 coins, but 3+3 = 2 coins is better).

function coinChange(coins, amount) {
  // dp[a] = fewest coins to make amount a. Infinity = "not yet known to be possible"
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // base case: 0 coins needed to make amount 0

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] !== Infinity) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1); // try using one of THIS coin
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Dry run: coinChange([1, 3, 4], 6) — the example above

dp[6] = 2, matching 3 + 3. The loop tries every coin at every amount and keeps the minimum — dp[3] getting to 1 (via the 3-coin, not two 1-coins) is what later lets dp[6] reuse that cheap subproblem instead of building up from dp[2].

Notice the loop order: for each amount, try every coin — this is "unbounded" DP (each coin can be reused any number of times), the exact same reuse idea as Combination Sum in the backtracking chapter, just solved by table-filling instead of exploring a tree.

Perfect Squares — coin change where the coins are squares

What is the fewest perfect squares (1, 4, 9, 16, ...) that add up to n? It is Coin Change with the coin set {1, 4, 9, ...} and unlimited use of each, and the same table applies: fewest[i] = 1 + min(fewest[i - r²]) over every square r² ≤ i, with fewest[0] = 0. Recognising that a problem is a known one in disguise is most of the skill here.

function numSquares(n) {
  const fewest = new Array(n + 1).fill(Infinity); // fewest[i] = fewest squares that sum to i
  fewest[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let root = 1; root * root <= i; root++) {
      fewest[i] = Math.min(fewest[i], fewest[i - root * root] + 1);
    }
  }
  return fewest[n];
}

Dry run: numSquares(12)

The answer 3 is 4 + 4 + 4; a greedy pick of the biggest square first would take 9 and then need three 1s, four squares. Time is O(n · √n), since each i tries at most √i squares, and space is O(n). A classical theorem says every positive integer is a sum of four squares, so the answer is never more than 4, which is a useful sanity check but not a reason to skip the table.

Coin Change II — the loop order decides what you count

Coin Change asked for the fewest coins. Coin Change II asks how many different combinations of coins sum to amount, where [1, 2] and [2, 1] are the same combination. The recurrence is again a sum, but now the order of the two loops changes the meaning of the answer.

function change(amount, coins) {
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1; // one way to make 0: take nothing
  for (const coin of coins) { // coins OUTSIDE: each combination is built in one coin order only
    for (let a = coin; a <= amount; a++) {
      ways[a] += ways[a - coin];
    }
  }
  return ways[amount];
}

function countOrderedWays(amount, coins) {
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (let a = 1; a <= amount; a++) { // amounts OUTSIDE: every order of the same coins counts
    for (const coin of coins) {
      if (coin <= a) ways[a] += ways[a - coin];
    }
  }
  return ways[amount];
}

With coins on the outside and amounts inside, you finish deciding about one coin before the next one is introduced, so each combination is built in one fixed coin order: counted once. With amounts on the outside and coins inside, every amount asks "what was my last coin?" for every coin, so 1 + 2 and 2 + 1 both count: you are counting sequences. For amount = 5 and coins = [1, 2, 5] the coin-outside version gives 4 combinations (5, 2+2+1, 2+1+1+1, 1+1+1+1+1), and the swapped loops give 9 ordered sequences.

Dry run: ways[0..5] after each coin, coins [1, 2, 5]

Notice that the inner loop runs upward here, so ways[a - coin] already includes uses of the same coin: that is what lets a coin be reused. The full treatment of this family, including how the loop direction flips for 0/1 choices, and the other counting variants such as Target Sum, is in the DP state machines and the knapsack family chapter. Time is O(amount · coins) and space O(amount).

Partition Equal Subset Sum — the backwards loop

Can an array be split into two subsets with equal sums? If the total is odd, no. Otherwise it is asking whether some subset sums to total / 2, which is a yes-or-no cousin of the table above with one big difference: each element may be used at most once. Let reachable[s] mean "some subset of the items seen so far sums to s". Adding an item x makes s reachable if s - x was reachable before this item.

function canPartition(nums) {
  const total = nums.reduce((sum, x) => sum + x, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const reachable = new Array(target + 1).fill(false); // reachable[s] = some subset sums to s
  reachable[0] = true;
  for (const x of nums) {
    for (let s = target; s >= x; s--) { // DOWNWARD: reachable[s - x] is still from BEFORE this item
      if (reachable[s - x]) reachable[s] = true;
    }
  }
  return reachable[target];
}

Dry run: [1, 5, 11, 5], target 11

11 is reachable (1 + 5 + 5, leaving 11 on the other side), so the answer is true. Time is O(n · total / 2) and space is O(total / 2). Note that this is pseudo-polynomial: it depends on the value of the sum, not only on the number of items.

Palindromic substrings — expand around every centre

Count the palindromic substrings of a string, or find the longest one. A palindrome is determined by its centre: grow outwards while the two ends match, and every step that succeeds is one more palindrome with the same centre. The centre is one of 2n - 1 places, n characters (odd lengths) and n - 1 gaps between characters (even lengths), and trying both kinds from every index covers them all.

function countSubstrings(s) {
  let count = 0;

  function expand(left, right) { // grow outwards while the ends match; each success is one palindrome
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  }

  for (let center = 0; center < s.length; center++) {
    expand(center, center); // odd length: the centre is a character
    expand(center, center + 1); // even length: the centre is a gap
  }
  return count;
}

function longestPalindrome(s) {
  let bestStart = 0, bestLen = 0;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    const len = right - left - 1; // the loop stepped one past the palindrome on each side
    if (len > bestLen) {
      bestLen = len;
      bestStart = left + 1;
    }
  }

  for (let center = 0; center < s.length; center++) {
    expand(center, center);
    expand(center, center + 1);
  }
  return s.slice(bestStart, bestStart + bestLen);
}

Dry run: countSubstrings("aaa")

Total 6 (three single letters, two "aa", one "aaa"). Time is O(n²): there are about 2n centres and each can expand O(n) steps, the worst case being a string of one repeated letter. Space is O(1) beyond the output. A different technique (Manacher's algorithm) does the same in O(n), but it is rarely asked for.

Triangle — let the rows be the table

A triangle of numbers has one entry in row 0, two in row 1, and so on. You start at the top and move to one of the two entries just below, left or right. Find the smallest path sum from top to bottom. Going top-down, the choice at each entry sends you into overlapping paths, so work bottom-up: the cheapest path from an entry down to the bottom is the entry itself plus the smaller of the two cheapest paths from the entries below it. Start with the last row, where the cheapest path is the entry, and fold the rows upward into one array.

function minimumTotal(triangle) {
  const best = [...triangle[triangle.length - 1]]; // best[j] = cheapest path from the row below down to the bottom, via j
  for (let row = triangle.length - 2; row >= 0; row--) {
    for (let j = 0; j <= row; j++) {
      best[j] = triangle[row][j] + Math.min(best[j], best[j + 1]); // step down-left or down-right
    }
  }
  return best[0];
}

Dry run: [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]

The answer is 11 (2 + 3 + 5 + 1). Time is O(n²) for n rows, which is the number of entries, and the extra space is O(n), one row. Because the array is reused row after row, the loop over j must go left to right: best[j] is overwritten using best[j] and best[j + 1], and best[j + 1] has not been overwritten yet at that point. Going right to left would read an already updated value.

A top-down template you can write on a whiteboard

The bottom-up tables above need you to see the fill order. When you cannot see it, or only some subproblems are ever reached, write the recursive definition first and add a cache. The recipe is four lines: a function of the whole state, a base case, a cache lookup, and a store before returning. Here is Coin Change from earlier written that way, with the cache keyed by the remaining amount:

function coinChangeTopDown(coins, amount) {
  const memo = new Map(); // key: remaining amount; value: fewest coins, or Infinity if impossible

  function solve(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining); // has(), not a truthiness test: 0 is a real answer

    let best = Infinity;
    for (const coin of coins) best = Math.min(best, solve(remaining - coin) + 1);
    memo.set(remaining, best);
    return best;
  }

  const result = solve(amount);
  return result === Infinity ? -1 : result;
}

Both versions solve the same distinct subproblems, at most amount of them, each doing coins.length work, so the time is O(amount · coins) in both. The rule for any memoized recursion is states × work per state.

Recognizing it in an unseen problem

• "Maximum/minimum/number of ways to…" over a sequence
• A brute-force recursive solution exists, but it's exponential because of repeated subproblems
• The answer at position i can be expressed using answers at earlier positions
• "Fewest/minimum number of coins/steps/jumps to reach X" with reusable choices → unbounded DP, same shape as Coin Change (Perfect Squares is Coin Change with square coins)
• "Number of ways to reach / decode / split" where the last move is one of a few kinds → add the counts of the states each kind comes from (Climbing Stairs, Decode Ways)
• "Can this prefix be split into pieces from a set?" → one boolean per prefix, looking back over the possible last piece (Word Break)
• Circular input → decide which element is left out and solve two linear problems (House Robber II)
• "Best subarray ending at i" where a negative or a zero changes everything → carry both the best and the worst value ending at i (Maximum Product Subarray)
• Counting combinations versus counting sequences → the order of the two loops decides which one you get (Coin Change II); 0/1 choices want the inner loop to run backwards (Partition Equal Subset Sum)
• If choices interact in only two dimensions (not "a sequence" but "a sequence + a budget," or two sequences compared against each other), that's the cue for 2D DP, next