Discussion on traversal order of complete knapsack in DP

First, let's review the definitions of several knapsack problems ：
01 knapsack ： Each item has only two states of taking or not taking
Completely backpack ： Each item can be taken infinitely many times
Multiple backpack ： Each item can be taken many times , But the times are different

as everyone knows ,01 Backpack uses two-dimensional dp You can exchange items and backpacks in any order , In one dimension dp If so, you must first stuff and then backpack, and the backpack is in reverse order , Otherwise, I will take the items again , The reason for traversal in reverse order is , It is essentially a traversal of a two-dimensional array , And the value of the lower right corner depends on the value of the upper left corner of the previous layer , Therefore, it is necessary to ensure that the value on the left is still the value of the previous level , Cover from right to left . Complete backpack two of complete backpack for The order of the cycle is OK .

Be careful , Pure complete knapsack is whether it can be summed up , namely dp The maximum weight that can be summed up is stored in the array （ Maximum ） It has nothing to do with the order of the elements that make up the sum , namely ： It's in order , No order ！ therefore , Some topics need more consideration if they involve order , Use Change for ② For example ：

Give you an array of integers coins Coins of different denominations , Give another integer amount Represents the total amount .

Please calculate and return the number of coin combinations that can be rounded up to the total amount . If no combination of coins can make up the total amount , return 0 .

Suppose that there are infinite coins of each denomination .

The subject data ensure that the results meet 32 Bit signed integer .

Example 1：

Input ：amount = 5, coins = [1, 2, 5]
Output ：4
explain ： There are four ways to make up the total 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
explain ： Use only face value 2 We can't make up the total amount of 3 .
Example 3：

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

Very little code ：

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

If we change the order ：

for (int j = 0; j <= amount; j++) {
     //  Traverse the backpack capacity 
    for (int i = 0; i < coins.size(); i++) {
     //  Traverse the items 
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

You will find that you cannot pass the test case , Here, draw a picture to explain the reason ：
Case one , Understand with code ：

The second case ：

Summary ：
  If you find the combination number, it's the outer layer for Loop through items , Inner layer for Traverse the backpack .
  If you find the permutation number, it's the outer layer for Traverse the backpack , Inner layer for Loop through items .