DAY 26 / 30 · WEEK 4

Dynamic Programming II

Goal of the day

• Recognize a max-of-choices recurrence — dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — and tell it apart from yesterday's pure-sum recurrence dp[i] = dp[i-1] + dp[i-2]. This is the first time in the course a DP table cell records a decision (skip this house or rob it) instead of just accumulating a running total.
• Recognize an unbounded DP, where a single "choice" (a coin denomination) can be reused an unlimited number of times, and see why that forces an inner loop over every option at each cell instead of a fixed O(1) lookback.
• Leave with two more DP shapes in your pattern library beyond fibonacci — by the end of Day 26 you should be able to look at a new problem and ask "is this a sum, a max-of-choices, or an unbounded min/max-over-options?" before writing a single line of code.

Concept

Day 25's recurrence never had to make a decision — dp[i] = dp[i-1] + dp[i-2] just adds two numbers together, every time, no matter what. Today's two problems both break that pattern in different ways, and recognizing which way a new problem breaks it is the actual interview skill.

House Robber, as a decision. Imagine walking down a street of houses, where robbing two houses next to each other trips the alarm. At each house you face exactly one choice: skip it and carry forward whatever you'd already secured up to the previous house, or rob it and add its value to whatever you'd secured two houses back (since the house right before it is now off-limits). You take whichever of those two options is worth more — that's dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Notice the shape: it's a max of two options, not a sum of two cells. Day 25's recurrence always uses both previous cells together; this one uses exactly one of them, whichever wins.

Coin Change, as an unbounded search. Now imagine making change for an amount using a fixed set of coin denominations, where you can use as many of any coin as you like — a handful of $1 coins is just as legal as a single $5. To find the minimum coins for amount amt, try every coin denomination that's small enough to fit: for a given coin c, if you use one of it, you still need to make amt - c with whatever's optimal there, plus this one coin. Take the cheapest option over every coin: dp[amt] = min(dp[amt - c] + 1) for every coin c ≤ amt. The word "unbounded" refers to the coins, not the amount — each coin can be reused without limit, which is exactly why the recurrence has to check every coin at every cell instead of reading a fixed two cells back like fibonacci or House Robber.

Lined up side by side, three structurally different recurrences:

• Day 25 (fibonacci-shaped): dp[i] = dp[i-1] + dp[i-2] — always sum both previous cells, no decision involved.
• House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — a decision between exactly 2 fixed options, still O(1) work per cell.
• Coin Change: dp[amt] = min(dp[amt-c] + 1) over every coin c — a decision between as many options as there are coins, so each cell costs O(number of coins), not O(1).

Same "sticky note" idea as Day 25 underneath all three — don't recompute a subproblem you've already solved — but the shape of what gets written on each sticky note, and how many earlier notes get read to fill in a new one, is different every time.

Diagram: House Robber — one cell's decision (max, not sum)

Diagram: Coin Change — the unbounded inner loop

Interactive visualization: filling the DP table

Two different recurrence shapes, same left-to-right table fill — watch what each cell reads and how many earlier cells it has to check.

1. House Robber — max(skip, rob) at every cell

2. Coin Change — the inner loop over every coin

The code

// 1. HOUSE ROBBER (LC 198) — O(1) space, two rolling variables.
//    prev2 stands in for "dp[i-2]", prev1 for "dp[i-1]", both seeded at 0
//    (robbing nothing before house 0 is worth 0 — the same trick as an
//    empty base case).
function houseRobber(nums) {
  let prev2 = 0, prev1 = 0;
  for (let i = 0; i < nums.length; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);  // skip vs. rob
    prev2 = prev1;                                  // slide the window forward
    prev1 = cur;
  }
  return prev1;
}

// 2. COIN CHANGE (LC 322) — 1D tabulated array, Infinity sentinel.
//    dp[amt] = fewest coins to make amt; dp[0] = 0 (base case); every
//    other slot starts at Infinity, meaning "not reachable yet."
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let amt = 1; amt <= amount; amt++) {
    for (const coin of coins) {                     // try EVERY coin — unbounded reuse
      if (coin <= amt && dp[amt - coin] + 1 < dp[amt]) {
        dp[amt] = dp[amt - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];  // never reached — no combination works
}

Line by line:

• houseRobber's prev2 and prev1 play the role of dp[i-2] and dp[i-1], both starting at 0 — that 0 represents "the best you could do robbing zero houses," which correctly falls out of the max on the very first iteration (max(0, 0 + nums[0]) = nums[0]). Every loop iteration is one decision: Math.max(prev1, prev2 + nums[i]) is literally "skip this house (keep prev1) or rob it (prev2 + this house's value)," and whichever is larger becomes the new rolling total.
• The prev2 = prev1; prev1 = cur; pair slides the window forward exactly like Day 25's fibOptimal — same O(1)-space trick, just applied to a max instead of a sum.
• coinChange seeds dp[0] = 0 (zero coins to make zero) and everything else at Infinity, meaning "no known way to make this amount yet." Infinity is deliberate: it makes any real coin count automatically beat an unreached amount in the comparison, and it survives arithmetic cleanly (Infinity + 1 is still Infinity) instead of silently looking like a valid small number the way a 0 sentinel would.
• The outer loop walks amt from 1 up to the target — bottom-up, same direction as every tabulated DP so far. The inner loop is what's new: for each amt, it tries every coin denomination that's small enough to fit (coin <= amt), because any of them could have been the last coin used to reach this amount, and there's no way to know which without checking. That inner loop is the direct consequence of coins being reusable without limit — "unbounded."
• The final line converts the internal Infinity sentinel back into the problem's actual contract: LeetCode expects -1 for "impossible," not Infinity. This check is not optional — skip it and the function returns Infinity for unreachable amounts instead of -1.

Dry run: houseRobber([2, 7, 9, 3, 1]) — rolling max

Final answer: 12. Trace which branch of the max won at each step to recover the actual houses: dp[4] = 12 came from the "rob" branch (dp[2] + nums[4] = 11 + 1), so house 4 is robbed; dp[2] = 11 also came from its "rob" branch (dp[0] + nums[2] = 2 + 9), so house 2 is robbed too; dp[0] is a base case, so house 0 is robbed. The optimal set is houses at indices 0, 2, and 4 — values 2, 9, and 1 — which sums to 12, with no two adjacent.

Dry run: coinChange([1, 2, 5], 11) — bottom-up table

Final answer: dp[11] = 3 — five plus five plus one (5 + 5 + 1 = 11, 3 coins). Note dp[10] = 2 (two fives) reuses coin 5 twice — that's the "unbounded" part in action.

Complexity

This is the key complexity distinction of the day: House Robber's inner work per cell is constant (just compare 2 numbers), so its total time is linear in the input size. Coin Change's inner work per cell scales with the number of coin denominations, so its total time is the product of two input sizes, not a sum of one.

Interview corner

• Why does House Robber's recurrence need "max," when Day 25's fibonacci-shaped recurrence used a plain sum? Fibonacci and Climbing Stairs are both "how many ways" or "how much total" problems where every path counts — you genuinely want everything added together. House Robber is an optimization problem with a hard constraint (no two adjacent houses): at each house you're choosing between two mutually exclusive outcomes, and only the better one survives into the next cell. Whenever a problem says "choose the best option among a small fixed set of alternatives," that's a signal you need max (or min) at each cell, not a sum.
  ↳ Common follow-up: "How would you recover which houses were actually robbed, not just the total?" — track which branch of the max won at each cell (a parallel "choice" array), then walk backward from the end.
• What happens if Coin Change has no valid combination for the target amount, and why does the code handle it correctly? Some amounts simply can't be made from the given coins (e.g. coins [2] can never make an odd amount). Because dp is seeded with Infinity everywhere except dp[0] = 0, an unreachable dp[amt] never gets overwritten by any coin's dp[amt-coin] + 1 — that comparison only replaces Infinity if the candidate is smaller, and Infinity + 1 stays Infinity forever. The final dp[amount] === Infinity ? -1 : dp[amount] check then converts that into the required -1.
  ⚠ Trap: seeding the array with 0 instead of Infinity is a common mistake — every unreachable amount would silently read as "0 coins needed," which is wrong but never crashes, so it's easy to miss in a quick test.
• Why doesn't a greedy "always pick the largest coin that fits" strategy work for Coin Change? Greedy is only correct for coin systems specifically designed for it (like US currency). Take coins [1, 3, 4] and amount 6: greedy grabs the largest coin that fits first — 4, leaving 2, then 1, then 1, for a total of 3 coins (4+1+1). But the true optimum is 2 coins (3+3). Greedy commits to the locally-best choice at each step and never reconsiders it, so it can lock in a decision that looks great in the moment but blocks a better global solution — exactly the kind of case DP handles correctly because it explores every option instead of committing early.
  ⚠ Trap: this is also the natural bridge to Day 27 — greedy algorithms are faster and simpler when they work, but tomorrow's lesson is specifically about how to recognize when a problem's structure guarantees greedy is safe, versus when (like here) it silently gives a wrong answer.
• Why is Coin Change's time complexity O(amount × coins) instead of just O(amount) like House Robber? House Robber's per-cell work is O(1) — always exactly 2 fixed lookbacks. Coin Change's per-cell work is O(coins) — it has to try every denomination because, unlike fibonacci's or House Robber's fixed 2-cell lookback, there's no way to know in advance which coin was optimal without checking them all. Multiply the O(amount) outer loop by the O(coins) inner loop and you get the product, not a sum — this is the first problem in the course where the DP table itself is 1D but the per-cell cost isn't constant.

How to talk through it out loud: name the recurrence shape before writing code — "this is a max over 2 fixed options" (House Robber) or "this is a min over every coin, so I need a nested loop" (Coin Change) — then state the base case and the sentinel value you're seeding the table with, and why (0 for "free," Infinity for "not yet reachable"). Interviewers are listening for whether you can name the shape of the recurrence and justify your sentinel choice before the code even runs, not just whether the final answer happens to be correct.

Practice problems

function houseRobber(nums) {
  let prev2 = 0, prev1 = 0;
  for (let i = 0; i < nums.length; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let amt = 1; amt <= amount; amt++) {
    for (const coin of coins) {
      if (coin <= amt && dp[amt - coin] + 1 < dp[amt]) {
        dp[amt] = dp[amt - coin] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  let best = 1;
  for (let i = 0; i < n; 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;
}

Quiz