Coin Change II

518.Coin Change II

Array

Dynamic Programming

Problem Statement:

Given an amount and an array of coins, return the number of combinations that make up that amount. You may assume you have infinite number of each kind of coin.

Example:

Input:

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

→

Output:

4

Algorithm:

1. Create 1D DP array for amount
2. Initialize dp[0] = 1 (base case)
3. For each coin, update possible amounts
4. Use current row for reusability

Complexity:

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

Java Solution:

// It's a classic 0/1 knapsack problem but with weight == value and a twist (WE CAN REUSE ITEMS)
// Instead of dp[i - 1][j] + dp[i - 1][j - coin] its dp[i - 1][j] + dp[i][j - coin]
// Because we can REUSE Items for the second check(including item) we dont go (i - 1) we just check the same row
// You should definitely memorize this one, its a good trick
// Because we can reuse items we don't have to go to previous row, and we can do it 1D
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];  // One-dimensional DP array
    dp[0] = 1;  // Base case: one way to make zero amount
    
    for (int coin : coins) {  // For each coin denomination
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i-coin];  // Add combinations from current row
        }
    }
    return dp[amount];
}

Python Solution:

def change(self, amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)  # Initialize DP array
    dp[0] = 1  # Base case: one way to make zero
    
    for coin in coins:  # For each coin
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]  # Add combinations from current row
            
    return dp[amount]

C++ Solution:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);  // Initialize DP array
        dp[0] = 1;  // Base case: one way to make zero
        
        for(int coin : coins) {  // For each coin
            for(int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];  // Add combinations from current row
            }
        }
        
        return dp[amount];
    }
};