Classic DP: Unbounded Knapsack Problem

518. 零钱兑换 II https://leetcode.cn/problems/coin-change-ii

518. Coin Change II https://leetcode.com/problems/coin-change-ii

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
518. Coin Change II	🟠
518. Coin Change II	🟠
518. Coin Change II	🟠

Prerequisite Knowledge

Before reading this article, you need to study:

• Core Framework of Dynamic Programming
• Detailed Explanation of the 0-1 Knapsack Problem

LeetCode Problem 322 "Coin Change I" is discussed as a classic dynamic programming example in Detailed Explanation of Dynamic Programming Techniques. This article discusses "Coin Change II," which is another typical variant of the knapsack problem. Previously, we have covered Classic Dynamic Programming: 0-1 Knapsack Problem and Knapsack Problem Variant: Equal Subset Partition.

Before reading this article, it is recommended that you have read the previous two articles, which cover dynamic programming and knapsack problem techniques. This article will continue the knapsack problem approach, presenting a variation of the knapsack problem.

Let's look at LeetCode Problem 518 "Coin Change II":

518. Coin Change II | LeetCode |

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.

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.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

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

The function signature we need to complete is as follows:

java 🟢

int change(int amount, int[] coins);

cpp 🤖

int change(int amount, vector<int>& coins);

python 🤖

def change(amount: int, coins: List[int]) -> int:

go 🤖

func change(amount int, coins []int) int

javascript 🤖

var change = function(amount, coins) {

};

We can transform this problem into the description of a knapsack problem:

Imagine a knapsack with a maximum capacity of amount. There is a series of items coins, where each item has a weight of coins[i]. The quantity of each item is unlimited. The question is, how many ways are there to fill the knapsack exactly?

This problem differs from the two knapsack problems we discussed earlier in one major aspect: the quantity of each item is unlimited. This is known as the "unbounded knapsack problem". It's not very complex; the main difference lies in the state transition equation.

Let's continue the analysis following the knapsack problem's description.

Solution Approach

The first step is to clarify two points: "State" and "Choice".

There are two states: "the capacity of the backpack" and "the items available to choose from". The choice is whether to "put the item in the backpack" or "not put it in the backpack". This is the typical pattern for backpack problems.

Once you understand the state and choice, the dynamic programming problem is almost solved. You just need to fit it into this framework:

for state1 in all_values_of_state1:
    for state2 in all_values_of_state2:
        for ...
            dp[state1][state2][...] = calculate(choice1, choice2...)

The second step is to define the dp array.

First, look at the "states" we identified earlier. There are two, so we need a two-dimensional dp array.

The definition of dp[i][j] is as follows:

If only the first i items are used (they can be reused), when the backpack capacity is j, there are dp[i][j] ways to fill the backpack.

In other words, translating this back to our problem:

If only the first i coins (counting from 1) in coins are used, to make the amount j, there are dp[i][j] ways to do so.

Based on this definition, we get:

The base case is dp[0][..] = 0, dp[..][0] = 1. i = 0 means no coin values are used, so obviously no amount can be made; j = 0 means the target amount is 0, and doing nothing is the only way to achieve this.

The final answer we want is dp[N][amount], where N is the size of the coins array.

The general pseudocode is as follows:

int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
    for j in [1..amount]:
        put item i in the backpack,
        do not put item i in the backpack
return dp[N][amount]

Step 3: Think about the logic of state transition based on the 'choice'.

Note that the special point of our problem is that the quantity of items is unlimited, so this is different from the previous 0-1 Knapsack Problem article.

If you do not include the i-th item in the knapsack, meaning you do not use the coin of value coins[i-1], then the number of ways to make up the amount j, dp[i][j], should be equal to dp[i-1][j], inheriting the previous result.

If you include the i-th item in the knapsack, meaning you use the coin of value coins[i-1], then dp[i][j] should be equal to dp[i][j-coins[i-1]].

Note

Since i in the definition starts counting from 1, the index of coins is i-1 when referring to the value of the i-th coin.

dp[i][j-coins[i-1]] is also not hard to understand. If you decide to use this coin, you should focus on how to make up the amount j - coins[i-1].

For example, if you want to use a coin of value 2 to make up an amount of 5, then if you know how to make up an amount of 3, adding a coin of value 2 will allow you to make up 5.

In summary, there are two choices, and what we want to find, dp[i][j], is the 'total number of ways to make up the amount'. Therefore, the value of dp[i][j] should be the sum of the results from the two choices mentioned above:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= amount; j++) {
        if (j - coins[i-1] >= 0) {
            dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i-1]];
        }
    }
}
return dp[N][W]

Note

Some readers might have a question here: Isn't it mentioned that coins can be reused? If I decide to "use the coin with the i-th denomination," how do I determine how many of these coins are used? Can a simple dp[i][j-coins[i-1]] cover the scenario of reusing the i-th coin?

For this question, I suggest you go back and carefully re-read our definition of the dp array, and then substitute this definition into dp[i][j-coins[i-1]] to see:

If only the first i items are used (and can be reused), when the backpack capacity is j-coins[i-1], there are dp[i][j-coins[i-1]] ways to fill the backpack.

See? dp[i][j-coins[i-1]] also allows you to use the i-th coin, so it already includes the scenario of reusing coins. You can be totally assured.

Finally, translate the pseudocode into actual code and handle some edge cases.

Here is the Java code I wrote, which fully translates the above thinking and handles some edge cases:

java 🟢

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // base case
        for (int i = 0; i <= n; i++) 
            dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++)
                if (j - coins[i-1] >= 0)
                    dp[i][j] = dp[i - 1][j] 
                            + dp[i][j - coins[i-1]];
                else 
                    dp[i][j] = dp[i - 1][j];
        }
        return dp[n][amount];
    }
}

cpp 🤖

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        // base case
        for (int i = 0; i <= n; i++) 
            dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++)
                if (j - coins[i-1] >= 0)
                    dp[i][j] = dp[i - 1][j] 
                            + dp[i][j - coins[i-1]];
                else 
                    dp[i][j] = dp[i - 1][j];
        }
        return dp[n][amount];
    }
};

python 🤖

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        # base case
        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(1, n + 1):
            for j in range(1, amount + 1):
                if j - coins[i-1] >= 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][amount]

go 🤖

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, amount+1)
    }
    // base case
    for i := 0; i <= n; i++ {
        dp[i][0] = 1
    }
    
    for i := 1; i <= n; i++ {
        for j := 1; j <= amount; j++ {
            if j - coins[i-1] >= 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[n][amount]
}

javascript 🤖

var change = function(amount, coins) {
    var n = coins.length;
    var dp = Array.from(Array(n + 1), () => Array(amount + 1).fill(0));
    // base case
    for(var i = 0; i <= n; i++)
        dp[i][0] = 1;

    for(var i = 1; i <= n; i++) {
        for(var j = 1; j <= amount; j++)
            if(j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else
                dp[i][j] = dp[i - 1][j];
    }
    return dp[n][amount];
}

Moreover, we can observe that the transition of the dp array only depends on dp[i][..] and dp[i-1][..]. Therefore, we can use dynamic programming space optimization techniques to further reduce the space complexity of the algorithm:

java 🟢

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        // base case
        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 1; j <= amount; j++)
                if (j - coins[i] >= 0)
                    dp[j] = dp[j] + dp[j-coins[i]];
        
        return dp[amount];
    }
}

cpp 🤖

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount + 1);
        // base case
        dp[0] = 1;
        for (int i = 0; i < n; i++)
            for (int j = 1; j <= amount; j++)
                if (j - coins[i] >= 0)
                    dp[j] = dp[j] + dp[j-coins[i]];
        
        return dp[amount];
    }
};

python 🤖

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [0] * (amount + 1)
        # base case
        dp[0] = 1
        for i in range(n):
            for j in range(1, amount + 1):
                if j - coins[i] >= 0:
                    dp[j] = dp[j] + dp[j - coins[i]]

        return dp[amount]

go 🤖

func change(amount int, coins []int) int {
    n := len(coins)
    dp := make([]int, amount+1)
    // base case
    dp[0] = 1
    for i := 0; i < n; i++ {
        for j := 1; j <= amount; j++ {
            if j-coins[i] >= 0 {
                dp[j] = dp[j] + dp[j-coins[i]]
            }
        }
    }
    return dp[amount]
}

javascript 🤖

var change = function(amount, coins) {
    var n = coins.length;
    var dp = new Array(amount + 1).fill(0);
    // base case
    dp[0] = 1;
    for (var i = 0; i < n; i++) {
        for (var j = 1; j <= amount; j++) {
            if (j - coins[i] >= 0) {
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
    }
    return dp[amount];
};

This solution follows the same logic as before, compressing the two-dimensional dp array into one dimension. The time complexity is O(N*amount), and the space complexity is O(amount).

With this, the coin change problem has also been solved using the framework of the knapsack problem.