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.

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.

Worked example: Longest Increasing Subsequence

// O(n²) — dp[i] = length of the longest increasing subsequence ENDING at i
function lengthOfLIS(nums) {
  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.

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];
}

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.

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
• 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