# Coin Change

- **Canonical ID**: `coin-change`
- **Canonical URL**: https://dsacheatsheet.com/problems/coin-change
- **Difficulty**: medium
- **Patterns**: 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/coin-change/

## 1. Core Invariant / The Trick

Bottom-up unbounded knapsack minimizing `dp[a]` (min coins for amount `a`). Initialize `dp = [amount + 1] * (amount + 1)` with `dp[0] = 0`, iterate `c` then `a >= c`: `dp[a] = min(dp[a], 1 + dp[a - c])`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(A * C)`
- **Space Complexity**: `O(A)`
- **Proof**: Evaluates C coins against each sub-amount up to A in a 1D array of length `A + 1`.

## 3. Minimal Idiomatic Code

### Python
```python
def coinChange(coins: list[int], amount: int) -> int:
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, amount + 1):
            if dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] <= amount else -1
```

### TypeScript
```typescript
export function coinChange(coins: number[], amount: number): number {
  const dp = new Int32Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) {
      dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] <= amount ? dp[amount] : -1;
}
```

### C++
```cpp
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int c : coins)
        for (int a = c; a <= amount; ++a)
            dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] <= amount ? dp[amount] : -1;
}
```

### Java
```java
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int c : coins)
        for (int a = c; a <= amount; a++)
            dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] <= amount ? dp[amount] : -1;
}
```

### Go
```go
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ { dp[i] = amount + 1 }
    for _, c := range coins {
        for a := c; a <= amount; a++ { dp[a] = min(dp[a], dp[a-c]+1) }
    }
    if dp[amount] <= amount { return dp[amount] }
    return -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Greedy largest-coin-first fails canonical non-US denominations like `coins=[1,3,4], amount=6` (`3+3=2` beats `4+1+1=3`).
- Returning `amount + 1` sentinel instead of `-1` when unreachable.

### Follow-ups
- Minimum BFS path in state graph `[0..amount]` can beat DP when `amount` is huge and largest coin allows early exit.