Coin Change II medium

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 number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The order of coins doesn’t matter.

Example 1

Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: There are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

Example 2

Input: amount = 3, coins = [2] Output: 0 Explanation: The amount of 3 cannot be made up just with coins of 2.

Steps

1. Initialization: Create a DP table dp of size amount + 1, initialized with 0. dp[i] will store the number of combinations to make amount i. We initialize dp[0] = 1 because there's one way to make amount 0 (using no coins).

2. Iteration: Iterate through each coin coin in coins.

3. Inner Iteration: For each coin, iterate through the DP table from the coin value up to the amount.

4. DP Update: For each index i in the inner loop, update dp[i] by adding dp[i - coin]. This represents adding the current coin to the combinations that already made up the amount i - coin.

5. Return: After iterating through all coins, dp[amount] will contain the total number of combinations to make the target amount.

Explanation

The dynamic programming approach builds up the solution incrementally. dp[i] represents the number of ways to make amount i. When considering a coin of value coin, we can add it to all the combinations that already make up the amount i - coin. Therefore, dp[i] is updated by adding dp[i - coin]. This ensures that we count all possible combinations without overcounting. The base case dp[0] = 1 is crucial because it represents the single way to make amount 0 (using no coins).

Code

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1

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

    return dp[amount]

Complexity

• Time Complexity: O(amount * len(coins)) - We have nested loops iterating through the amount and the coins.
• Space Complexity: O(amount) - The DP table dp takes linear space proportional to the amount.