Editorial: Coin Change

1 Intuition

This is a classic unbounded knapsack problem. For each amount from 1 to target, we try using each coin and take the minimum number needed. We build up the solution from smaller amounts to larger ones.

2 Approach

1. Create DP array where dp[i] = min coins needed for amount i 2. Initialize dp[0] = 0 (need 0 coins for amount 0) 3. For each amount from 1 to target: - Try each coin (if coin <= amount) - dp[amount] = min(dp[amount], dp[amount-coin] + 1) 4. Return dp[target] (-1 if impossible)

3 Complexity Analysis

**Time Complexity:** O(amount × coins.length) **Space Complexity:** O(amount) - DP array This bottom-up approach is efficient and avoids recursion overhead.

4 Solution Code

def coinChange(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return -1 if dp[amount] == float("inf") else dp[amount]

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

5 Code Walkthrough

For coins=[1,5,11], amount=15: - dp[0]=0 - dp[1]=1 (use coin 1) - dp[2]=2 (use coin 1 twice) - dp[5]=1 (use coin 5) - dp[11]=1 (use coin 11) - dp[15]=3 (use 11+1+1 or 5+5+5) Result: 3