Coin Change - Dynamic Programming Explained Visually

Why it works

Every amount smaller than the target is a subproblem, and each is solved exactly once and reused by every larger amount - that reuse is the whole trick of DP. n amounts × k coins each gives O(n·k) time and O(n) space.

The problem

Given an integer array coins representing coin denominations and an integer amount, return the fewest number of coins needed to make up that amount. If not possible, return -1.

Hints

• dp[i] = minimum coins to make amount i.
• dp[0] = 0 (base case), dp[i] = infinity initially.
• For each amount, try each coin: dp[amt] = min(dp[amt], dp[amt-coin] + 1).
• The bottom-up approach processes amounts from 1 to target.

Test cases

Reference starter code

def coin_change(coins, amount):
    # Bottom-up DP
    pass

print(coin_change([1, 5, 11], 15))  # 3
print(coin_change([1, 5, 11], 11))  # 1
print(coin_change([2], 3))          # -1
print(coin_change([1], 0))          # 0

More challenges in this topic

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.