Overview

Session 5 opened with two spaced-repetition reviews (Merge K Sorted Lists and Climb Stairs), then covered Coin Change as the canonical unbounded-knapsack problem, and finished with House Robber II as a variation that reduces a circular constraint to two independent linear subproblems.

Concept

Unbounded Knapsack

The classic 0/1 knapsack lets you use each item at most once. Unbounded knapsack removes that restriction — each item may be used any number of times. The recurrence changes one index:

Coin Change is unbounded knapsack where all item values are 1 (each coin counts as one coin) and you minimize instead of maximize. The 2D table collapses to 1D because all coins are considered at every amount:

dp[i] = min over all coins c of (dp[i - c] + 1)
dp[0] = 0
dp[i] initialized to Infinity (sentinel for "not yet reachable")

Complexity: O(amount × |coins|) time, O(amount) space. No way to reduce space further — lookback depth equals the largest coin denomination, which can be as large as amount.

DP State Design Rule

DP state should represent the best answer to a complete subproblem. A constrained state (“dp[i] = best if you must rob house i”) forces unbounded lookback because you can’t reconstruct the full picture from one constrained slice alone. Either use the unconstrained best-so-far, or track two parallel constrained states that together cover all cases.

Implementation

Coin Change

const IMPOSSIBLE = -1

function minCoinCount(coins: number[], target: number): number {
  const counts = new Array(target + 1)
  counts[0] = 0
  for (let i = 1; i <= target; ++i) {
    counts[i] = Math.min(...coins.map(c => (counts[i - c] ?? Infinity) + 1))
  }
  const result = counts[target]
  return result === Infinity ? IMPOSSIBLE : result
}

Notes on James’s original:

• Used counts[i - c] ?? Infinity to handle coins larger than i (negative index returns undefined in JS). Clever and correct.
• Had new Array(target) (off-by-one) and counts.at(-1) ?? IMPOSSIBLE — the ?? doesn’t catch Infinity, so impossible cases returned Infinity instead of -1.

House Robber II (circular)

function robCircular(houses: number[]) {
  return Math.max(robLinear(houses.slice(0, -1)), robLinear(houses.slice(1)))
}

function robLinear(houses: number[]) {
  if (houses.length === 0) return 0
  if (houses.length === 1) return houses[0]

  let prev2 = houses[0]
  let prev1 = Math.max(houses[0], houses[1])

  for (let i = 2; i < houses.length; ++i) {
    const curr = Math.max(prev2 + houses[i], prev1)
    prev2 = prev1
    prev1 = curr
  }

  return prev1
}

Problems

Merge K Sorted Lists (spaced rep — heaps)

Problem: Given k sorted linked lists, merge them into one sorted list. Return the head.

Approach: Seed a min-heap with the head of each list. Each step: extract the minimum node, append it to the result, push its .next back into the heap if non-null. O(N log k).

Solution:

type Head<T> = { value: T; next: Head<T> | null }
type Comparator<T> = (a: T, b: T) => number

function mergeSortedLists<T>(heads: Head<T>[], comparator: Comparator<T>) {
  const heap = new Heap<Head<T>>((a, b) => comparator(a.value, b.value))
  for (const h of heads) heap.insert(h)

  const sentinel: Head<T> = { value: null as any, next: null }
  let tail = sentinel

  let node: Head<T> | null
  while ((node = heap.extractMin()) != null) {
    tail.next = node
    tail = node
    if (node.next) heap.insert(node.next)
  }

  return sentinel.next
}

Key miss: James forgot to heap.insert(node.next) after extraction — the algorithm only drained the initial k heads without advancing into each list.

Climb Stairs (spaced rep — DP)

Problem: Climb n stairs 1 or 2 steps at a time. How many distinct ways?

Approach: Fibonacci with base cases dp[1]=1, dp[2]=2.

James’s off-by-one: loop condition i < n should be i <= n. Same error as Session 4 — habit to build: trace the boundary case by hand after writing the loop.

Coin Change

Problem: Given coin denominations and a target, return the minimum number of coins to make the target. Each denomination may be used unlimited times. Return -1 if impossible.

Approach: Unbounded knapsack. dp[i] = min(dp[i-c] + 1) for each coin c. Initialize dp[0]=0, rest to Infinity.

Key bug to avoid: Infinity ?? -1 short-circuits to Infinity because Infinity is not nullish. Check result === Infinity explicitly.

House Robber II (circular)

Problem: Houses are in a circle. Can’t rob two adjacent houses. Maximize loot.

Approach: Reduce to two linear subproblems: rob(houses[0..n-2]) and rob(houses[1..n-1]). Take the max. This works because houses 0 and n-1 can’t coexist, so you solve once excluding each.

James’s bugs in robLinear:

1. Loop bound i <= houses.length (should be i < houses.length) — accesses undefined
2. Recurrence max(prev2 + h[i], prev1 + h[i]) — the “skip” branch should not add h[i]
3. Init of dp[1] was houses[1] instead of max(houses[0], houses[1])

Root cause of bugs 2 & 3: tried to define dp[i] as “best if you must rob house i” — a constrained state that forces unbounded lookback and can’t be composed into a clean recurrence.