LeetCode 322: Coin Change

Problem Restatement

We are given:

coins
amount

coins contains coin denominations.

We may use each coin any number of times.

Return the minimum number of coins needed to make exactly amount.

If it is impossible, return:

-1

The official constraints include:

(github.com)

Input and Output

Function shape:

def coinChange(coins: list[int], amount: int) -> int:
    ...

Examples

Example 1:

coins = [1, 2, 5]
amount = 11

One optimal choice:

5 + 5 + 1

Coin count:

3

Output:

3

Example 2:

coins = [2]
amount = 3

We cannot form 3 using only 2.

Output:

-1

Example 3:

coins = [1]
amount = 0

We need zero coins.

Output:

0

First Thought: Greedy Choice

A natural idea is:

Always take the largest possible coin.

For:

coins = [1, 2, 5]
amount = 11

this works:

5 + 5 + 1

But greedy fails in general.

Example:

coins = [1, 3, 4]
amount = 6

Greedy chooses:

4 + 1 + 1

using 3 coins.

But the optimal answer is:

3 + 3

using only 2 coins.

So we need dynamic programming.

Key Insight

Suppose we already know the minimum coins needed for smaller amounts.

For amount x, if we use coin c last, then before using c we must already have formed:

x - c

So:

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

over all usable coins c.

This gives a direct recurrence.

DP Definition

Let:

dp[x]

mean:

Minimum number of coins needed to form amount x.

Base case:

dp[0] = 0

because zero coins are needed to form amount zero.

Initialize all other states as impossible.

inf

Transition

For every amount:

x

try every coin:

coin

If:

x >= coin

then we can form x by adding one coin after forming:

x - coin

Transition:

dp[x] = min(dp[x], dp[x - coin] + 1)

Example Walkthrough

Use:

coins = [1, 2, 5]
amount = 11

Start:

dp[0] = 0

All others:

inf

For amount 1:

So:

dp[1] = 1

For amount 2:

So:

dp[2] = 1

For amount 5:

So:

dp[5] = 1

Eventually:

dp[11] = 3

from:

5 + 5 + 1

Algorithm

1. Create a DP array of size amount + 1.
2. Set all values to infinity.
3. Set:

   dp[0] = 0
4. For each amount from 1 to amount:
   • Try every coin.
   • Update the minimum value.
5. If dp[amount] is still infinity, return -1.
6. Otherwise return dp[amount].

Correctness

We prove by induction on the amount.

Base case:

dp[0] = 0

is correct because zero coins are needed to form amount zero.

Now assume all values:

dp[0], dp[1], ..., dp[x - 1]

are correct.

To form amount x, consider the last coin used in an optimal solution. Suppose that coin is c.

Then the remaining amount is:

x - c

and the number of coins used before the last coin must be:

dp[x - c]

by the induction hypothesis.

Therefore the optimal solution for x has value:

dp[x - c] + 1

for some valid coin c.

The algorithm checks every possible coin and takes the minimum, so it computes exactly the optimal number of coins for amount x.

Thus every dp[x] is correct, including dp[amount].

If no combination can form the target, the value remains infinity and the algorithm correctly returns -1.

Complexity

Let:

Implementation

class Solution:
    def coinChange(
        self,
        coins: list[int],
        amount: int,
    ) -> int:

        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for current in range(1, amount + 1):
            for coin in coins:
                if current >= coin:
                    dp[current] = min(
                        dp[current],
                        dp[current - coin] + 1,
                    )

        if dp[amount] == float("inf"):
            return -1

        return dp[amount]

Code Explanation

Create the DP array.

dp = [float("inf")] * (amount + 1)

Every amount is initially impossible.

Base case:

dp[0] = 0

Now compute amounts from small to large.

for current in range(1, amount + 1):

Try every coin.

for coin in coins:

If the coin can fit:

if current >= coin:

then update the answer.

dp[current] = min(
    dp[current],
    dp[current - coin] + 1,
)

At the end:

if dp[amount] == float("inf"):
    return -1

because no valid combination exists.

Otherwise return the minimum coin count.

BFS Interpretation

This problem can also be viewed as shortest path search.

Each amount is a node.

From amount x, using coin c moves to:

x + c

Every edge has cost 1.

The goal is to reach amount using the fewest steps.

Dynamic programming is usually simpler and faster here.

Testing

def run_tests():
    s = Solution()

    assert s.coinChange([1, 2, 5], 11) == 3
    assert s.coinChange([2], 3) == -1
    assert s.coinChange([1], 0) == 0
    assert s.coinChange([1], 2) == 2
    assert s.coinChange([2, 5, 10, 1], 27) == 4
    assert s.coinChange([186, 419, 83, 408], 6249) == 20
    assert s.coinChange([3, 4], 6) == 2

    print("all tests passed")

run_tests()

Test meaning: