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 and Min-Cost Staircase is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]=2Coin Change: Why Greedy Fails
Greedy (always pick the largest coin that fits) fails for coin change. Example: coins=[1, 3, 4], amount=6. Greedy picks 4 then 1+1 = 3 coins. Optimal is 3+3 = 2 coins. Greedy works for standard denominations (1, 5, 10, 25 cents) because they happen to satisfy the greedy property. But for arbitrary coin sets, DP is required. This is a classic interview point — stating that greedy fails and explaining why shows strong analytical thinking.
# Greedy failure example:
# coins=[1,3,4], amount=6
# Greedy: 4 (rem=2), 1 (rem=1), 1 (rem=0) -> 3 coins
# Optimal: 3 (rem=3), 3 (rem=0) -> 2 coins
def coin_change_greedy_wrong(coins, amount):
coins_sorted = sorted(coins, reverse=True)
count = 0
for coin in coins_sorted:
while amount >= coin:
amount -= coin
count += 1
return count if amount == 0 else -1
print('Greedy:', coin_change_greedy_wrong([1,3,4], 6)) # 3 (WRONG)
print('DP: ', coin_change([1,3,4], 6)) # 2 (CORRECT)Coin Change II: Count the Ways
Coin Change II (LeetCode #518) asks for the number of ways to make the amount (not the minimum count). The recurrence changes: instead of min, use sum. dp[i] += dp[i-coin] for each coin. The fill order matters: to count each combination once, iterate coins in the outer loop and amounts in the inner loop. Reversing the loops counts permutations instead of combinations (a different problem).
def coin_change_ii(coins, amount):
# dp[i] = number of ways to make amount i
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0: use no coins
# Outer loop: coins -- ensures each coin type processed once
for coin in coins:
# Inner loop: amounts
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
print(coin_change_ii([1, 2, 5], 5)) # 4: [1,1,1,1,1],[1,1,1,2],[1,2,2],[5]
print(coin_change_ii([2], 3)) # 0: impossible
print(coin_change_ii([10], 10)) # 1
# Key: coin outer, amount inner = COMBINATIONS (unordered)
# Reverse (amount outer, coin inner) = PERMUTATIONS (ordered)Min-Cost Staircase: The Problem
Min Cost Climbing Stairs (LeetCode #746) gives a staircase where each step has a cost. You can climb 1 or 2 steps at a time. Find the minimum cost to reach the top (one step beyond the last stair). You can start at step 0 or step 1 for free. This problem elegantly combines the climbing-stairs recurrence with the coin-change cost-minimisation pattern, making it a natural bridge between the two.
# cost = [10, 15, 20]
# Pay cost[i] to leave step i
# You can step to i+1 or i+2
# Goal: reach top (index 3) with minimum cost
# Path options:
# Start at 0: cost 10, go to 2: cost 20, done -> 30
# Start at 1: cost 15, go to 3: done -> 15 <- OPTIMAL
# Start at 0: cost 10, go to 1: cost 15 -> 25
cost = [10, 15, 20]
# Optimal: start at step 1, pay 15, jump to top -> cost = 15
print('Expected:', 15)Min-Cost Staircase: Recurrence
Define dp[i] = minimum cost to reach step i. You arrive at step i by paying cost[i-1] (from step i-1) or cost[i-2] (from step i-2). So dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Base cases: dp[0] = 0 (start before the stairs, free), dp[1] = 0 (can also start at step 1, free). The answer is dp[n] where n = len(cost).
def min_cost_climbing_stairs(cost):
n = len(cost)
# dp[i] = minimum cost to reach step i
# Steps 0 to n; step n is the top (goal)
dp = [0] * (n + 1)
# dp[0] = 0 (free to start here)
# dp[1] = 0 (free to start here)
for i in range(2, n + 1):
dp[i] = min(dp[i-1] + cost[i-1], # step from i-1
dp[i-2] + cost[i-2]) # jump from i-2
return dp[n]
print(min_cost_climbing_stairs([10, 15, 20])) # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1])) # 6Min-Cost Staircase: Space Optimisation
Since dp[i] only depends on dp[i-1] and dp[i-2], we can reduce space to O(1) with two variables, just like Fibonacci. Replace the array with prev2 and prev1. Update them at each step. This is a standard one-liner optimisation that interviewers expect after you present the O(n) table solution. Always mention it proactively: 'We can reduce this to O(1) space since we only need the last two values.'
def min_cost_optimised(cost):
n = len(cost)
prev2, prev1 = 0, 0 # dp[0] and dp[1]
for i in range(2, n + 1):
curr = min(prev1 + cost[i-1], prev2 + cost[i-2])
prev2, prev1 = prev1, curr
return prev1
print(min_cost_optimised([10, 15, 20])) # 15
print(min_cost_optimised([1,100,1,1,1,100,1,1,100,1])) # 6
# Alternative: directly use cost array as rolling storage
def min_cost_v2(cost):
n = len(cost)
for i in range(2, n):
cost[i] += min(cost[i-1], cost[i-2])
return min(cost[-1], cost[-2])
from copy import deepcopy
cost_test = [10,15,20]
print(min_cost_v2(deepcopy(cost_test))) # 15Alternative DP Formulation
Some problems have multiple valid DP formulations. For min-cost staircase, you can define dp[i] = minimum cost to LEAVE step i (pay cost[i] and choose to go to i+1 or i+2). Then dp[i] = cost[i] + min(dp[i+1], dp[i+2]) filling right to left, and the answer is min(dp[0], dp[1]). Both formulations are correct. Practise articulating which formulation you chose and why — this demonstrates DP fluency.
def min_cost_alternative(cost):
n = len(cost)
# dp[i] = min cost when starting FROM step i
# Fill right to left
dp = cost[:] + [0] # dp[n] = 0 (already at top)
for i in range(n - 1, -1, -1):
# Pay cost[i], then choose i+1 or i+2
if i + 2 <= n:
dp[i] = cost[i] + min(dp[i+1], dp[i+2])
else:
dp[i] = cost[i] + dp[i+1]
# Can start at step 0 or step 1
return min(dp[0], dp[1])
print(min_cost_alternative([10, 15, 20])) # 15
print(min_cost_alternative([1,100,1,1,1,100,1,1,100,1])) # 6Connecting Coin Change and Staircase
Both coin change and min-cost staircase are instances of the same DP pattern: at each step, make a choice from a finite set of options, and optimise an objective over the sequence of choices. The differences are cosmetic: coin change tracks count (add 1 per coin), staircase tracks cost (add cost[i] per step). Recognising this shared structure lets you solve new DP problems by mapping them to familiar templates.
# Shared pattern:
# dp[state] = optimise(dp[prev_state_1] + cost_1,
# dp[prev_state_2] + cost_2, ...)
# Coin change: dp[amount] = min(1 + dp[amount - coin] for coin in coins)
# Min stair: dp[step] = min(cost[step-1]+dp[step-1], cost[step-2]+dp[step-2])
# Max path sum: dp[cell] = max(dp[top], dp[left]) + grid[cell]
# House robber: dp[house] = max(dp[house-1], dp[house-2] + value[house])
# All four are the SAME pattern with different:
# - State representation
# - Number of choices per state
# - Objective (min/max)
# - Transition cost
print('DP pattern: state + choices + objective + cost = template')Minimum Number of Perfect Squares
Perfect Squares (LeetCode #279) asks for the minimum number of perfect squares (1, 4, 9, 16, ...) that sum to n. This is exactly coin change where 'coins' are perfect square numbers. Generate all perfect squares up to n, then run coin change. DP gives O(n * sqrt(n)) time. Lagrange's Four-Square Theorem tells us the answer is at most 4, which also allows an O(sqrt(n)) mathematical approach — but DP is the expected solution.
import math
def num_squares(n):
# Generate all perfect squares up to n
squares = [i*i for i in range(1, int(math.sqrt(n)) + 1)]
# Coin change with squares as 'coins'
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
for sq in squares:
if i >= sq:
dp[i] = min(dp[i], 1 + dp[i - sq])
return dp[n]
print(num_squares(12)) # 3: 4+4+4
print(num_squares(13)) # 2: 4+9
print(num_squares(1)) # 1: 1Debugging DP: Common Mistakes
Common DP bugs: wrong base case (dp[0] set incorrectly), wrong fill order (accessing a value that hasn't been computed yet), off-by-one in state definition (dp[i] is cost TO reach i vs cost to LEAVE i), and not returning -1 when infinity remains (impossible cases). Always test on the simplest cases (empty input, single element, target=0) before testing larger inputs.
# Common DP debugging checklist:
# 1. Base case: what is dp[0]? dp[1]? Are they correct?
# 2. State definition: write it in English before coding
# 3. Recurrence: trace manually on a 3-element example
# 4. Fill order: dependency arrows point left/up? Fill left/up first
# 5. Infinity check: return -1 or 0 when dp[target] == inf?
# 6. Array bounds: dp has size n+1 for 0..n, or n for 0..n-1?
# Quick test template:
def test_coin_change():
assert coin_change([1], 0) == 0 # base case
assert coin_change([1], 1) == 1 # single coin
assert coin_change([2], 3) == -1 # impossible
assert coin_change([1,5,6,9], 11) == 2
print('All tests passed!')
test_coin_change()Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: coin change minimum-count DP (unbounded knapsack) and why greedy fails, coin change II for counting combinations with coin-outer/amount-inner order, and min-cost staircase with both left-to-right and right-to-left formulations. Next up we explore 1D DP patterns with house robber, Kadane's algorithm, and word break.
Frequently asked questions
Is the “Coin Change and Min-Cost Staircase” lesson free?
Yes — the full text of “Coin Change and Min-Cost Staircase” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Coin Change and Min-Cost Staircase” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All 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