Classic DP: Unbounded Knapsack Problem
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 518. Coin Change II | 🟠 |
| 518. Coin Change II | 🟠 |
Prerequisite Knowledge
Before reading this article, you should first learn:
LeetCode Problem 322 "Coin Change I" has been discussed as a classic example of dynamic programming in Detailed Dynamic Programming Patterns. This article discusses Coin Change II, which is another typical variation of the knapsack problem. We have previously covered Classic Dynamic Programming: 0-1 Knapsack Problem and Knapsack Variation: Equal Subset Partition.
Before reading this article, it is recommended that you have read the previous two articles to understand the patterns of dynamic programming and knapsack problems. This article will continue to follow the knapsack problem patterns and illustrate a variation of the knapsack problem.
Consider 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 <= 3001 <= coins[i] <= 5000- All the values of
coinsare unique. 0 <= amount <= 5000
The function signature we need to complete is as follows:
int change(int amount, int[] coins);int change(int amount, vector<int>& coins);def change(amount: int, coins: List[int]) -> int:func change(amount int, coins []int) intvar change = function(amount, coins) {
};We can transform this problem into a description format of the knapsack problem:
There is a knapsack with a maximum capacity of amount, and a series of items coins, each with a weight of coins[i]. The quantity of each item is unlimited. How many ways are there to fill the knapsack exactly?
The main difference between this problem and the previous two knapsack problems is that the quantity of each item is unlimited, which is known as the "Complete Knapsack Problem". It's not complicated; it just involves a slight change in the state transition equation.
Let's continue with the analysis using the knapsack problem description format.