Coin Change

Python Java C++

def coinChange(coins, amount):
    # Initialize dp array with amount + 1 size
    dp = [0] + [float('inf')] * amount
    
    # Build solution for each amount from 1 to target
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                diff = i - coin
                if dp[diff] == -1: continue
                dp[i] = min(dp[i], 1 + dp[diff])
        
        if dp[i] == float('inf'): dp[i] = -1
            
    return dp[amount]

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Initialize dp array with amount + 1 size
        int[] dp = new int[amount + 1];
        
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++)
            dp[i] = Integer.MAX_VALUE;
        
        // Build solution for each amount from 1 to target
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    int diff = i - coin;
                    if (dp[diff] == -1) continue;   
                    dp[i] = Math.min(dp[i], 1 + dp[diff]);
                }
            }
            
            if (dp[i] == Integer.MAX_VALUE) dp[i] = -1;    
        }   
        
        return dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        // Initialize dp array with amount + 1 size
        vector dp(amount + 1);
        
        dp[0] = 0;
        for (int i = 1; i <= amount; i++)
            dp[i] = INT_MAX;
        
        // Build solution for each amount from 1 to target
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    int diff = i - coin;
                    if (dp[diff] == -1) continue;
                    if (dp[diff] != INT_MAX)
                        dp[i] = min(dp[i], 1 + dp[diff]);
                }
            }
            
            if (dp[i] == INT_MAX) dp[i] = -1;
        }
        
        return dp[amount];
    }
};

Problem Statement

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

Category: Dynamic Programming | Difficulty: Medium

Detailed Explanation

Approach

Using bottom-up dynamic programming, we build solutions for all amounts from 1 to target amount, using previously calculated results.

Key Concepts

1. DP Array: dp[i] represents minimum coins needed for amount i
2. Base Case: dp[0] = 0 (zero coins needed for zero amount)
3. Invalid Case: -1 represents impossible amounts

Algorithm Steps

1. Initialize dp array:

   • Set dp[0] = 0
   • Set all other values to MAX_VALUE

2. For each amount from 1 to target:

   • Try each coin denomination
   • Only use coin if it's less than current amount
   • Update if we find a better solution

Visual Example

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

dp array evolution:
[0,1,2,3,4,5,6,7,8,9,10,11]  # Using coin 1
[0,1,1,2,2,3,3,4,4,5,5,6]    # Using coin 2
[0,1,1,2,2,1,2,2,3,3,2,3]    # Using coin 5

Final answer: 3 (5 + 5 + 1)

Time and Space Complexity

• Time Complexity: O(amount * number of coins)
• Space Complexity: O(amount)

Why Initialize with MAX_VALUE?

• Allows us to find minimum values using Math.min()
• Gets converted to -1 if no solution is found
• Could also use amount + 1 as alternative

Edge Cases

• amount = 0: return 0
• No valid solution: return -1
• Single coin denomination
• When amount is less than smallest coin