One-Dimensional DP

How to think about it

Name dp[i] in plain language (min coins for amount i; max money through house i). Express it using earlier cells. Fill in an order that respects dependencies. Compress space if only last few cells matter.

Template shapes

Shape	Core move	Notes
Linear	dp[i] from dp[i-1], dp[i-2]	Robber, stairs
Unbounded knapsack-ish	Loop coins outer or inner	Coin change
LIS style	dp[i]=max over j<i	O(n²) baseline

Complexity baseline

Typically O(n) or O(n·W); space O(n) or O(1) rolled.

From template to problem

1. Write dp[i] meaning + base cases.
2. Write the transition.
3. Choose loop bounds carefully.
4. Return dp[target] (or max over dp).

/** 1D DP template: Coin Change (fewest coins). dp[x] = min coins for amount x. */
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! >= INF ? -1 : dp[amount]!;
}

/** 1D DP template: Coin Change (fewest coins). dp[x] = min coins for amount x. */
export function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array<number>(amount + 1).fill(INF);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const c of coins) {
      if (c <= x) dp[x] = Math.min(dp[x]!, dp[x - c]! + 1);
    }
  }
  return dp[amount]! >= INF ? -1 : dp[amount]!;
}