Coin Change Theory

Deriving the recurrence, space choices, and exploring variants: minimum coins, counting ways, and order-sensitive formulations.

State

dp[a] = min coins to form a

Transition

dp[a] = min(dp[a-c]+1)

Counting Variant

Add ways via accumulation

1. Minimum Coins Recurrence

dp[0] = 0
for a in 1..A:
  dp[a] = INF
  for coin in coins:
    if coin <= a:
      dp[a] = min(dp[a], dp[a-coin] + 1)

Use a large sentinel (Infinity) to represent unreachable states. Answer is dp[A] unless still Infinity.

2. Complexity

Time: O(n × A) where n = number of coin types.
Space: O(A)
Optimization: early break when coin > a if coins sorted.

3. Counting Ways Variant

ways[0] = 1
for coin in coins:
  for a in coin..A:
    ways[a] += ways[a-coin]

Iterating coins outermost prevents counting permutations multiple times (combinations). Swap loop order (amount outer, coins inner) to count ordered sequences.

4. Edge Cases & Notes

Duplicate denominations: remove or ignore (no benefit).
Zero or negative coins: validate input.
Large target: consider pruning unreachable by gcd of coins.
When greedy (like canonical US coins) works, DP still generalizes.

← Simulation Next: LIS →