Classical dynamic programming: complete knapsack problem

Finish reading this article , You can go and get the following questions ： [518. Change II](https://leetcode-cn.com/problems/coin-change-2) **-----------** Change 2 It's a variant of another typical knapsack problem , As we have said earlier [ Classical dynamic programming ：0-1 Knapsack problem ](https://labuladong.gitbook.io/algo). ** I hope you've read the first two articles **, I've seen the dynamic programming and knapsack problem , This article continues with the knapsack problem , List a variant of the knapsack problem . This article talks about LeetCode The first 518 Title Coin Change 2, The title is as follows ：  ```java int change(int amount, int[] coins); ``` PS： To Coin Change 1, Before we did [ Detailed explanation of dynamic programming routine ](https://labuladong.gitbook.io/algo) Yes . ** We can turn this problem into a knapsack problem **： There's a backpack , The maximum capacity is `amount`, There's a range of things `coins`, The weight of each item is `coins[i]`,** The number of each item is unlimited **. How many ways are there , It can fill the backpack exactly ？ This problem and the two knapsack problems we talked about earlier , One of the biggest differences is , The number of each item is infinite , This is also the legend of 「** Complete knapsack problem **」, Nothing big , It's just a little change in the state transfer equation . The following is a description of the knapsack problem , Continue to analyze according to the process . PS：** I've seriously written about 100 Many original articles , Hand brush 200 Daoli is the subject , All published in [labuladong It's a copy of the algorithm ](https://links.jianshu.com/go?to=https%3A%2F%2Flabuladong.gitbook.io%2Falgo%2F), Continuous update **. Suggest collecting ,** Write the title in the order of my article **, After mastering all kinds of algorithms, it will be like a fish in water to throw it into the sea of questions . ### Thinking of problem solving ** The first step is to be clear about two things ,「 Status 」 and 「 Choice 」**. There are two states , Namely 「 The capacity of the backpack 」 and 「 Optional items 」, The choice is 「 Put it in a backpack 」 perhaps 「 Not in a backpack 」 Well , The knapsack problem is like this . Understand the state and the choice , The dynamic programming problem is basically solved , Just put this frame around and it's done ： ```python for Status 1 in Status 1 All values of ： for Status 2 in Status 2 All values of ： for ... dp[ Status 1][ Status 2][...] = Calculation ( Choice 1, Choice 2...) ``` ** The second step is to be clear about `dp` The definition of arrays **. First of all, take a look at what you just found 「 Status 」, There are two , In other words, we need a two-dimensional `dp` Array . `dp[i][j]` The definition of is as follows ： If only before use `i` Items , When the backpack capacity is `j` When , Yes `dp[i][j]` There are ways to fill a backpack . In other words , Translation back to our title means ： ** If only `coins` In front of `i` The face value of a coin , If you want to make up the amount `j`, Yes `dp[i][j]` Planting method **. After the above definition , You can get ： base case For `dp[0][..] = 0, dp[..][0] = 1`. Because if you don't use any denomination , You can't come up with any amount ; If the target amount is 0, So “ Governing by inaction ” It's the only way to make it up . The answer we want to get is `dp[N][amount]`, among `N` For `coins` The size of the array . The general idea of PN code is as follows ： ```python int dp[N+1][amount+1] dp[0][..] = 0 dp[..][0] = 1 for i in [1..N]: for j in [1..amount]: Put the goods i Put it in a backpack , Don't put things i Put it in a backpack return dp[N][amount] ``` ** The third step , According to 「 Choice 」, Thinking about the logic of state transition **. Be careful , The special point of our problem is that the number of items is infinite , So this is different from the previous article on backpacking . ** If you don't put this `i` Put an item in a backpack **, That means you don't use `coins[i]` This coin in denomination , So make up the denomination `j` Method number of `dp[i][j]` Should be equal to `dp[i-1][j]`, Inherit the result before . ** If you put this first `i` Items are packed into a backpack **, That means you use `coins[i]` This coin in denomination , So `dp[i][j]` Should be equal to `dp[i][j-coins[i-1]]`. First of all, because `i` It's from 1 Starting , therefore `coins` The index of is `i-1` The second is the third `i` The face value of a coin . `dp[i][j-coins[i-1]]` It's not hard to understand , If you decide to use this denomination , Then we should pay attention to how to make up the amount `j - coins[i-1]`. For example , You want to use the face value of 2 To make up the sum of 5, So if you know, make up the amount 3 Methods , Plus a denomination of 2 The coin of , No, we can come up with 5 Yes . ** To sum up, there are two choices , And what we want is `dp[i][j]` yes 「 How many tricks are there 」, therefore `dp[i][j]` The value of should be the sum of the above two choices **： ```java 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] ``` ** The last step , Translate pseudo code into code , Deal with some boundary conditions **. I use Java Written code , Translate all the above ideas , And dealt with some boundary problems ： ```java int change(int amount, int[] coins) { int n = coins.length; int[][] dp = amount 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]; } ``` and , We can find through observation that ,`dp` The transfer of an array is only as good as `dp[i][..]` and `dp[i-1][..]` About , So you can compress the State , Further reduce the space complexity of the algorithm ： ```java int change(int amount, int[] coins) { int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; // base case 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]; } ``` This solution is exactly the same as before , Two dimensional `dp` The array is compressed into one dimension , Time complexity O(N\*amount), Space complexity O(amount). thus , This change exchange problem is also solved through the framework of knapsack problem . **＿＿＿＿＿＿＿＿＿＿＿＿＿** my [ Online e-books ](https://labuladong.gitbook.io/algo) Yes 100 An original article , Hands with brushes 200 Daoli is the subject , Suggest collecting ！ Corresponding GitHub [ Algorithms warehouse ](https://github.com/labuladong/fucking-algorithm) You've got 70k star, Welcome