Solution Explanation: Coin Change II

This problem asks to find the number of combinations of coins that sum up to a given amount. We can efficiently solve this using dynamic programming.

Approach:

The core idea is to build a table (or array) where each entry dp[i] represents the number of ways to make up the amount i using the available coins.

1. Initialization: We initialize dp[0] = 1, as there's one way to make an amount of 0 (using no coins). All other entries are initially 0.

2. Iteration: We iterate through each coin denomination coin and then through each amount i from coin up to the target amount. For each i, we add the number of ways to make i - coin (using the same coins) to the current number of ways to make i (dp[i]). This is because we can form amount i by taking one coin and combining it with the ways to make i - coin.

3. Result: After iterating through all coins, dp[amount] will hold the total number of ways to make up the target amount.

Time Complexity Analysis:

The outer loop iterates through each coin (let's say there are m coins). The inner loop iterates from the coin value up to the target amount (n). Therefore, the time complexity is O(m*n).

Space Complexity Analysis:

We use a 1D DP array of size n+1. Therefore, the space complexity is O(n).

Code Examples (Optimized): The optimized solution uses a 1D DP array to reduce space complexity.

Python:

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1  # Base case: one way to make amount 0
 
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
 
    return dp[amount]
 

Java:

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
 
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

C++:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
 
        for (int coin : coins) {
            for (int i = coin; i <= amount; ++i) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

Go:

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
 
    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i - coin]
        }
    }
    return dp[amount]
}

Javascript:

var change = function(amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
 
    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
};

TypeScript:

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
 
    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

These optimized versions maintain the same time complexity but use less space compared to the 2D DP approach. They all effectively solve the coin change II problem by iteratively building up the number of combinations for each possible amount.