力扣题解 动态规划（3）

0.1完全背包

/ 先遍历物品，在遍历背包
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++) {
     // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) {
     // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    
    test_CompletePack();
}

518. 零钱兑换 II

是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

dp[j]：凑成总金额j的货币组合数为dp[j]

所以递推公式：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++) {
     // 遍历物品
            for (int j = coins[i]; j <= amount; j++) {
     // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

C++测试用例有两个数相加超过int的数据，所以需要在if里加上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++) {
     // 遍历背包
            for (int j = 0; j < nums.size(); j++) {
     // 遍历物品
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
    
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

70. 爬楼梯

class Solution {
    
public:
    int climbStairs(int n) {
    
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
     // 遍历背包
            for (int j = 1; j <= m; j++) {
     // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了。

322. 零钱兑换

而本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！

    // 版本一
    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++) {
     // 遍历物品
                for (int j = coins[i]; j <= amount; j++) {
     // 遍历背包
                    if (dp[j - coins[i]] != INT_MAX) {
     // 如果dp[j - coins[i]]是初始值则跳过
                        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                    }
                }
            }
            if (dp[amount] == INT_MAX) return -1;
            return dp[amount];
        }
    };

对于遍历方式遍历背包放在外循环，遍历物品放在内循环也是可以的，我就直接给出代码了

    // 版本一
    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++) {
     // 遍历物品
                for (int j = coins[i]; j <= amount; j++) {
     // 遍历背包
                    if (dp[j - coins[i]] != INT_MAX) {
     // 如果dp[j - coins[i]]是初始值则跳过
                        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                    }
                }
            }
            if (dp[amount] == INT_MAX) return -1;
            return dp[amount];
        }
    };