Classic DP patterns

Implement coin change, 0/1 knapsack, and climbing stairs bottom-up — three patterns that cover most 1D DP problems.

Three workhorses. Each appears in a wide family of real problems; recognising the underlying pattern matters more than memorising the code.

Three canonical problems

Python — editable, runs in your browser

# ── 1. Coin change ──────────────────────────────────────────────────────────
# Given coin denominations and an amount, find the minimum number of coins
# needed to reach that amount. Return -1 if it is impossible.

def coin_change(coins, amount):
  INF = float("inf")
  dp = [INF] * (amount + 1)
  dp[0] = 0                           # 0 coins needed for amount 0
  for a in range(1, amount + 1):
      for c in coins:
          if c <= a and dp[a - c] + 1 < dp[a]:
              dp[a] = dp[a - c] + 1
  return dp[amount] if dp[amount] != INF else -1

# ── 2. 0/1 Knapsack ─────────────────────────────────────────────────────────
# Given item weights and values, and a capacity W, find the maximum value
# achievable by selecting items (each item can be taken at most once).

def knapsack(weights, values, capacity):
  n = len(weights)
  # dp[i][w] = best value using items 0..i-1 with weight limit w
  dp = [[0] * (capacity + 1) for _ in range(n + 1)]
  for i in range(1, n + 1):
      w_i, v_i = weights[i - 1], values[i - 1]
      for w in range(capacity + 1):
          # skip item i-1
          dp[i][w] = dp[i - 1][w]
          # take item i-1 (if it fits)
          if w_i <= w:
              take = dp[i - 1][w - w_i] + v_i
              if take > dp[i][w]:
                  dp[i][w] = take
  return dp[n][capacity]

# ── 3. Climbing stairs ───────────────────────────────────────────────────────
# You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?
# Equivalent to Fibonacci with a rolling window.

def climb_stairs(n):
  if n <= 2:
      return n
  prev2, prev1 = 1, 2
  for _ in range(3, n + 1):
      prev2, prev1 = prev1, prev1 + prev2
  return prev1

# ── Tests ────────────────────────────────────────────────────────────────────
print("Coin change")
print(coin_change([1, 5, 6, 9], 11))   # 2  (coins 5+6)
print(coin_change([2], 3))             # -1 (impossible)
print(coin_change([1, 2, 5], 11))      # 3  (5+5+1)

print()
print("0/1 Knapsack")
# items: weight 2 value 3, weight 3 value 4, weight 4 value 5, weight 5 value 6
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10 (items 0+1+2 or 0+3?)
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9  (items 1+2 or 1+3?)

print()
print("Climbing stairs")
for i in range(1, 8):
  print(f"  n={i}: {climb_stairs(i)} ways")

Coin change: the recurrence

dp[a] = minimum coins to make amount a. For each coin c, if we use one coin of denomination c, the remaining problem is a - c, already solved. So dp[a] = min over all coins c of (dp[a - c] + 1). Fill from dp[0] = 0 upward.

The key insight: unlike 0/1 knapsack, coins can be reused — this is an unbounded DP. The inner loop iterates over denominations, not a "take or skip" binary choice.

0/1 knapsack: take or skip

The 2D table captures a choice at each item. dp[i][w] considers only items 0 through i-1 with a weight budget of w. Two options at item i-1:

Skip: dp[i][w] = dp[i-1][w] — same budget, one fewer item to consider.
Take (if it fits): dp[i][w] = dp[i-1][w - weight[i-1]] + value[i-1].

Take the maximum of the two. The "1" in "0/1" means each item can be included at most once — hence using dp[i-1] (previous row) when taking, not dp[i].

Space optimisation for knapsack: process the weight loop in reverse when using a single 1D array. This prevents an item from being counted twice in the same pass, which would turn 0/1 into unbounded knapsack.

Climbing stairs: disguised Fibonacci

ways(n) = ways(n-1) + ways(n-2). Exactly Fibonacci with different base cases. The rolling window brings space to O(1). This pattern appears whenever "the number of ways to reach state n equals the sum of ways to reach two adjacent states."

Where to go next

Next: 2D DP — longest common subsequence, edit distance, and unique paths in a grid, where the recurrence operates on a full 2D table rather than a 1D array.

Finished reading? Mark it complete to track your progress.

Three canonical problems

Coin change: the recurrence

0/1 knapsack: take or skip

Climbing stairs: disguised Fibonacci

Where to go next

On this page