Coin Change I

322.Coin Change

Array

Dynamic Programming

Problem Statement:

Given an array of coins denominations and an amount, return the fewest number of coins needed to make up that amount. Return -1 if the amount cannot be made up by any combination of the coins.

Example:

Input:

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

→

Output:

3

Algorithm:

1. Create DP array of size amount + 1
2. Initialize with MAX_VALUE (unreachable state)
3. For each amount try all coins
4. Track minimum coins needed

Complexity:

Time: O(amount * coins) | Space: O(amount)

Java Solution:

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];  // DP array size amount + 1

    dp[0] = 0;  // Base case: 0 coins needed for amount 0
    for (int i = 1; i < dp.length; i++) 
        dp[i] = Integer.MAX_VALUE;  // Initialize with unreachable state
  
    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]);  // Take minimum coins needed
            }
        }
        
        if (dp[i] == Integer.MAX_VALUE) dp[i] = -1;  // Mark unreachable amounts   
    }   
    
    return dp[amount];
}

Python Solution:

def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)  # Initialize with infinity
    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

C++ Solution:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // Base case
        
        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];
    }
};