Coin Change
You are given an integer array `coins` representing coin denominations and an integer `amount`. Return the fewest number of coins needed to make up `amount`, or `-1` if it is impossible. **Core Insight:** Classic unbounded knapsack / bottom-up DP. Define `dp[i]` as the minimum number of coins needed to make amount `i`. Base case: `dp[0] = 0`. For each amount from 1 to `amount`, try every coin: if `coin <= i`, then `dp[i] = min(dp[i], dp[i - coin] + 1)`. **Algorithm:** Initialize `dp` array of size `amount + 1` with `Infinity` (or `amount + 1` as a sentinel). Set `dp[0] = 0`. For each `i` from 1 to `amount`, for each `coin`: if `coin <= i` update `dp[i] = min(dp[i], dp[i - coin] + 1)`. Return `dp[amount]` if it's not Infinity, else -1. **Why bottom-up:** Each sub-problem `dp[i]` depends only on smaller sub-problems, so filling the table left to right guarantees all dependencies are resolved. **Complexity:** Time O(amount × coins) — two nested loops. Space O(amount) — the DP table.
Constraints
- •
1 ≤ coins.length ≤ 12 - •
0 ≤ amount ≤ 10⁴
def coinChange(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1