代码随想录第40天|动态规划

完全背包

完全背包物品可以无限使用

01背包核心代码

01背包中的二维dp数组的两个for遍历可颠倒, 而一维dp数组的一定先遍历物品再遍历背包容量
状态转移方程(背包容量一定为递减)

完全背包核心代码 (只在完全背包中一维dp数组嵌套顺序可颠倒, 实际题目需要确定遍历顺序)

状态转移方程(先物品, 再背包, 并且为递增, 横向更新数值)
由于都是由前一个状态推导, 所以只在纯完全背包问题中可以颠倒, 区别是行更新或者列更新
状态转移方程(先背包, 再物品, 递增顺序, 且为纵向更新)

518. 零钱兑换 II
在这里插入图片描述

递推公式: dp[j] += dp[j - coins[i]]

概括物体和背包的遍历情况

先遍历物品(coins)后遍历背包(amount), 物品 coins[i] 只能在本次循环中添加, 下一次循环才添加coins[i+1], 只有一种: coins[i] coins[i + 1]
先遍历背包后遍历物品时, coins[i] coins[i + 1] 与 coins[i + 1] 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 = 0; j <= amount; j++) {//遍历背包
                if (j - coins[i] >= 0)
                    dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ
在这里插入图片描述

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        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] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) //防两个int相加会溢出
                    dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};