# LeetCode 322: Coin Change

## Problem Restatement

We are given:

```python
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:

```python
-1
```

The official constraints include:

| Constraint | Value |
|---|---:|
| `1 <= coins.length <= 12` |
| `1 <= coins[i] <= 2^31 - 1` |
| `0 <= amount <= 10^4` |

([github.com](https://github.com/doocs/leetcode/blob/main/solution/0300-0399/0322.Coin%20Change/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Coin denominations and target amount |
| Output | Minimum number of coins |
| Unlimited reuse | Yes |
| Impossible case | Return `-1` |

Function shape:

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

## Examples

Example 1:

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

One optimal choice:

```text
5 + 5 + 1
```

Coin count:

```python
3
```

Output:

```python
3
```

Example 2:

```python
coins = [2]
amount = 3
```

We cannot form `3` using only `2`.

Output:

```python
-1
```

Example 3:

```python
coins = [1]
amount = 0
```

We need zero coins.

Output:

```python
0
```

## First Thought: Greedy Choice

A natural idea is:

> Always take the largest possible coin.

For:

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

this works:

```text
5 + 5 + 1
```

But greedy fails in general.

Example:

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

Greedy chooses:

```text
4 + 1 + 1
```

using `3` coins.

But the optimal answer is:

```text
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:

```python
x - c
```

So:

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

over all usable coins `c`.

This gives a direct recurrence.

## DP Definition

Let:

```python
dp[x]
```

mean:

> Minimum number of coins needed to form amount `x`.

Base case:

```python
dp[0] = 0
```

because zero coins are needed to form amount zero.

Initialize all other states as impossible.

```python
inf
```

## Transition

For every amount:

```python
x
```

try every coin:

```python
coin
```

If:

```python
x >= coin
```

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

```python
x - coin
```

Transition:

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

## Example Walkthrough

Use:

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

Start:

```python
dp[0] = 0
```

All others:

```python
inf
```

For amount `1`:

| Coin | Result |
|---|---|
| `1` | `dp[0] + 1 = 1` |

So:

```python
dp[1] = 1
```

For amount `2`:

| Coin | Result |
|---|---|
| `1` | `dp[1] + 1 = 2` |
| `2` | `dp[0] + 1 = 1` |

So:

```python
dp[2] = 1
```

For amount `5`:

| Coin | Result |
|---|---|
| `1` | `5` coins |
| `2` | `3` coins |
| `5` | `1` coin |

So:

```python
dp[5] = 1
```

Eventually:

```python
dp[11] = 3
```

from:

```text
5 + 5 + 1
```

## Algorithm

1. Create a DP array of size `amount + 1`.
2. Set all values to infinity.
3. Set:
   ```python id="m3e7lt"
   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:

```python
dp[0] = 0
```

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

Now assume all values:

```python
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:

```python
x - c
```

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

```python
dp[x - c]
```

by the induction hypothesis.

Therefore the optimal solution for `x` has value:

```python
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:

| Symbol | Meaning |
|---|---|
| `n` | Number of coin types |
| `A` | Target amount |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(nA)` | Every amount tries every coin |
| Space | `O(A)` | One DP array |

## Implementation

```python
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.

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

Every amount is initially impossible.

Base case:

```python
dp[0] = 0
```

Now compute amounts from small to large.

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

Try every coin.

```python
for coin in coins:
```

If the coin can fit:

```python
if current >= coin:
```

then update the answer.

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

At the end:

```python
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:

```python
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

```python
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:

| Test | Why |
|---|---|
| `[1,2,5], 11` | Standard example |
| `[2], 3` | Impossible case |
| `[1], 0` | Base case |
| `[1], 2` | Repeated reuse |
| Mixed coins | Larger reachable target |
| Large official-style test | Performance check |
| `[3,4], 6` | Greedy would fail with other coin systems |