Coin Change 2

Dynamic ProgrammingUnbounded Knapsack

25 min

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.

Example

Example 1:

Coins:

Amount:5

Combinations:4

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Solution

This problem asks for the number of combinations to make up an amount, which is different from the first Coin Change problem that asks for the minimum number of coins. We can solve this using dynamic programming.

Let `dp[i]` be the number of combinations to make amount `i`. We initialize `dp[0] = 1` (there's one way to make amount 0: use no coins). Then, for each coin, we iterate through the amounts and update the `dp` table.

Algorithm Steps (DP)

Create a DP array `dp` of size `amount + 1` and initialize all elements to 0.
Set `dp[0] = 1`.
For each `coin` in `coins`:
Iterate from `i = coin` to `amount`.
Update `dp[i] = dp[i] + dp[i - coin]`.
The final answer is `dp[amount]`.

Recurrence Relation

dp[i] = dp[i] + dp[i - coin]

Coins:

DP Table (Number of Combinations)

Step: 1 / 15

Coin Change 2 Solution


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]