随想录一刷Day44——动态规划

Day44_动态规划

18. 完全背包

完全背包与01背包的区别是，01背包每个物品只能装入一次，而完全背包可以对同一物品多次添加。
01背包一维形式内层循环考虑容量时是从大到小遍历，防止一个物品被多次添加。
而完全背包内层循环容量需要从小到大遍历，保证每个物品可被选中多次。

19. 零钱兑换 II

518. 零钱兑换 II
思路：

1. dp[j] 表示凑成面值为 j 的组合数为 dp[j]
2. $dp[j]=\sum dp[j-coins[i]]$，当前面值的组合数为不加入当前硬币的所有组合数之和(只需要在这些组合中再放入当前硬币即可)
3. 初始化 dp[0] = 1; // 凑成面值为 0 的面值的方法数为 1
4. 遍历顺序，外层循环是硬币面值才能避免硬币顺序问题导致的组合数重复

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int coins_size = coins.size();
        vector<int> dp(amount + 1, 0);
        dp[0] = 1; // 凑成面值为 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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

20. 组合总和 Ⅳ

377. 组合总和 Ⅳ
思路：

思路同上题，不过本题求得是排列，不同得组合顺序算不同得方案，于是两层循环得顺序就得调换了，外层是背包的容量，内层让数字重复遍历不同的容量，从而获取所有的排列数。

注意，题目提到：题目数据保证答案符合 32 位整数范围。
于是真的就坑你一手，既然有这样的保证，那么方案数超出的整数范围的部分抛弃就好，添加筛选条件dp[j] < INT_MAX - dp[j - nums[i]]

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int nums_size = nums.size();
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= target; ++j) {
            for (int i = 0; i < nums_size; ++i) {
                if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15