# 经典动态规划：完全背包问题

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

518. Coin Change II | 🟠 |

Prerequisites

Before reading this article, you should learn:

LeetCode problem #322 "Coin Change I" was discussed in the previous article Dynamic Programming Patterns Explained as a classic example of dynamic programming. In this article, we will discuss "Coin Change II," which is another variant of the typical knapsack problem. We have already covered Classic Dynamic Programming: 0-1 Knapsack Problem and Knapsack Problem Variant: Equal Subset Partition.

**Before reading this article, I hope you have read the previous two articles**, familiarized yourself with the patterns of dynamic programming and knapsack problems. This article continues to follow the knapsack problem pattern and introduces 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:4Explanation: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:0Explanation: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 implement 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) int`

```
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]]`

.注

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]
```

注

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:

```
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];
}
}
```

```
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];
}
};
```

```
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]
```

```
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]
}
```

```
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];
}
```

Furthermore, by observing, we can see that the transition of the `dp`

array only depends on `dp[i][..]`

and `dp[i-1][..]`

. Therefore, we can use the previously discussed Dynamic Programming Space Optimization Technique to further reduce the space complexity of the algorithm:

```
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];
}
}
```

```
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];
}
};
```

```
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]
```

```
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]
}
```

```
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.