Coin Change

Problem Statement

You’ve got coins of different denominations and a target amount. Find the minimum number of coins needed to make that amount. If impossible, return -1. This medium-level DP quest is a coin collector’s challenge—spend efficiently!

Example

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

Output: 3 (5+5+1)

Input: coins = [2], amount = 3

Output: -1 (no combination works)

Input: coins = [1, 3, 4], amount = 10

Output: 3 (4+3+3)

Code

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
            

def coin_change(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 dp[amount] if dp[amount] != float('inf') else -1

# Example usage
print(coin_change([1, 2, 5], 11))  # 3
print(coin_change([2], 3))  # -1
            

function coinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example usage
console.log(coinChange([1, 2, 5], 11));  // 3
console.log(coinChange([2], 3));  // -1
            

Explanation

• DP Insight: dp[i] = min coins to make amount i.
• Steps: Start with infinity, update with min of current or using a coin.
• Flow Example ([1,2,5],11): dp[5]=1, dp[10]=2, dp[11]=3 (5+5+1).
• Why It Works: Builds minimal solutions bottom-up.

Note