35. Coin Change

You are given an integer array coins representing coin denominations and an integer amount representing a total amount of money. Return the fewest number of coins needed to make up that amount. If that amount cannot be made up by any combination of the coins, return -1.

Input: coins = [1,5,11], amount = 11
Output: 1
Explanation: 11 = 11

Input: coins = [2], amount = 3
Output: -1

Input: coins = [1], amount = 0
Output: 0

Problem Breakdown:

1. Create a DP array where dp[i] represents the minimum coins needed to make amount i. Initialize all values to amount + 1 (impossible placeholder). dp[0] = 0 since 0 coins are needed for amount 0.

• dp = [amount + 1] * (amount + 1)
  dp[0] = 0

2. For each amount from 1 to target, try every coin. If the coin fits (coin <= current amount), update dp[i] with the minimum of its current value and dp[i - coin] + 1.

• for i in range(1, amount + 1):
      for coin in coins:
          if coin <= i:
              dp[i] = min(dp[i], dp[i - coin] + 1)

3. After filling the DP table, check if dp[amount] is still the impossible value. If so, return -1. Otherwise return dp[amount].

• return dp[amount] if dp[amount] <= amount else -1

Summary:

Bottom-up DP where dp[i] is the minimum coins for amount i. For each amount, try all coins and take the minimum. If dp[amount] is unreachable, return -1.

Time and Space Complexity:

Time Complexity: O(n * amount) - where n is the number of coin denominations.

Space Complexity: O(amount) - for the DP array.

Python Solution:

def coinChange(coins, amount):
    dp = [amount + 1] * (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] <= amount else -1

JavaScript Solution:

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

Java Solution:

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];
    }
}