Coin Change and Min-Cost Staircase
Formulate the coin-change and min-cost-climbing-stairs recurrences, choose the right DP direction, and trace through the table manually.
Coin Change: The Problem
Coin Change (LeetCode #322) gives you coin denominations and a target amount. Find the minimum number of coins needed to make the exact amount. You have unlimited coins of each denomination. This is a classic unbounded knapsack variant — each item (coin) can be used any number of times. It is one of the most important DP problems because it tests your ability to formulate a recurrence from scratch.
# Problem examples:
# coins=[1,5,6,9], amount=11 -> 2 (5+6 or 2+9? no: 5+6=11 YES)
# coins=[2], amount=3 -> -1 (impossible)
# coins=[1,2,5], amount=11 -> 3 (5+5+1)
# coins=[186,419,83,408], amount=6249 -> 20
# Key choices:
# - Try each coin denomination at each step
# - Minimum coins = 1 + minimum(coins to make amount - coin)
# - If amount < 0: impossible
# - If amount = 0: done (0 coins)
print('Coin change: unbounded knapsack, find minimum count')Coin Change: Recurrence Derivation
Define dp[i] = minimum coins to make amount i. For each amount i, try using each coin c: if i >= c, then dp[i] = min(dp[i], 1 + dp[i-c]). The '1' accounts for the coin we just used; dp[i-c] is the optimal solution for the remaining amount. This assumes infinite coins. Base case: dp[0] = 0. Initialise all other entries to infinity to represent 'not yet achievable'.
def coin_change(coins, amount):
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin and dp[i - coin] != float('inf'):
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2
print(coin_change([2], 3)) # -1
print(coin_change([1, 2, 5], 11)) # 3
# Trace dp for coins=[1,5] amount=6:
# dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=1, dp[6]=2All lessons in this course
- Recognising DP: Overlapping Sub-Problems
- Top-Down DP with Memoisation
- Bottom-Up DP with Tabulation
- Coin Change and Min-Cost Staircase