Dynamic planning for solving problems (3)

0.1 Completely backpack

/  Go through the items first , Walking through the backpack 
void test_CompletePack() {
    
    vector<int> weight = {
    1, 3, 4};
    vector<int> value = {
    15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) {
     //  Traverse the items 
        for(int j = weight[i]; j <= bagWeight; j++) {
     //  Traverse the backpack capacity 
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    
    test_CompletePack();
}

518. Change for II

It's a typical knapsack problem , There is no limit to the number of coins , I knew it was a complete backpack

When there are several ways to fill a backpack , It's critical to recognize the traversal order .

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 .

dp[j]： Make up the total amount j The number of currency combinations is dp[j]

So the recurrence formula ：dp[j] += dp[j - coins[i]];

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

377. Combinatorial summation Ⅳ

C++ There are two numbers in the test case that add up to more than int The data of , So you need to be in if Riga dp[i] < INT_MAX - dp[i - num].

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

70. climb stairs

class Solution {
    
public:
    int climbStairs(int n) {
    
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
     //  Traverse the backpack 
            for (int j = 1; j <= m; j++) {
     //  Traverse the items 
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

In the code m It means you can climb at most m A stair , In the code m Change to 2 That's the question 70. Climbing stairs can AC The code of .

322. Change for

The problem is to ask for the minimum number of coins , It doesn't matter whether the coins are combined or arranged ！ So the two one. for The order of the cycle can be any way ！

    //  Version of a 
    class Solution {
    
    public:
        int coinChange(vector<int>& coins, int amount) {
    
            vector<int> dp(amount + 1, INT_MAX);
            dp[0] = 0;
            for (int i = 0; i < coins.size(); i++) {
     //  Traverse the items 
                for (int j = coins[i]; j <= amount; j++) {
     //  Traverse the backpack 
                    if (dp[j - coins[i]] != INT_MAX) {
     //  If dp[j - coins[i]] If it is the initial value, skip 
                        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                    }
                }
            }
            if (dp[amount] == INT_MAX) return -1;
            return dp[amount];
        }
    };

 For the traversal mode, the traversal knapsack is placed in the outer loop , It's OK to traverse items and put them in inner circulation , I'll just give the code 

    //  Version of a 
    class Solution {
    
    public:
        int coinChange(vector<int>& coins, int amount) {
    
            vector<int> dp(amount + 1, INT_MAX);
            dp[0] = 0;
            for (int i = 0; i < coins.size(); i++) {
     //  Traverse the items 
                for (int j = coins[i]; j <= amount; j++) {
     //  Traverse the backpack 
                    if (dp[j - coins[i]] != INT_MAX) {
     //  If dp[j - coins[i]] If it is the initial value, skip 
                        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                    }
                }
            }
            if (dp[amount] == INT_MAX) return -1;
            return dp[amount];
        }
    };