MediumDynamic Programming

Coin Change II

Explanation & Solution

Description

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 answer is guaranteed to fit into a signed 32-bit integer.

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

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique
0 <= amount <= 5000

Approach

Dynamic Programming pattern

1. Define the DP Array

Create an array dp of size amount + 1, initialized to 0
dp[i] represents the number of combinations that make up amount i
Set dp[0] = 1 because there is exactly one way to make amount 0: use no coins

2. Iterate Over Each Coin

Loop through each coin denomination in the coins array
For each coin, we update the DP array to include combinations using that coin
Processing coins in the outer loop ensures we count combinations, not permutations

3. Update the DP Array

For each coin, iterate j from coin to amount
For each j, add dp[j - coin] to dp[j]
This means: the number of ways to make amount j increases by the number of ways to make j - coin (since we can add one more of the current coin)

4. Return the Result

After processing all coins, dp[amount] contains the total number of combinations
Return dp[amount]

Key Insight

By iterating coins in the outer loop and amounts in the inner loop, each combination is counted exactly once (e.g., [1,2] and [2,1] are treated as the same combination)
This is an unbounded knapsack variant where we can use each coin unlimited times

Time

O(n * amount) where n is the number of coin denominations

Space

O(amount) for the 1D DP array

Visualization

Input:

Dynamic Programmingamount = 5, coins = [1,2,5]

Press play to start DP animation

ComputingDependencyFilledEmpty

12 steps

Solution Code

Coin Change

Longest Increasing Subsequence