Coin Change

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Examples

The brute-force approach

Try every combination of coins recursively. At each step, try placing each coin denomination and recurse on the remaining amount. Track the minimum depth that reaches amount 0.

def solve(remaining):
    if remaining == 0: return 0      # made it
    if remaining < 0: return inf     # overshot

    best = inf
    for coin in coins:
        result = solve(remaining - coin)
        best = min(best, 1 + result)
    return best

answer = solve(amount)
return -1 if answer == inf else answer

Exponential, the same sub-amounts are recomputed many times via different coin paths. solve(amount−coin) is called repeatedly with the same argument. The overlapping subproblems are the classic DP signal.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

For each target amount, which single coin + a previously solved sub-amount gives the smallest total?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.