DAY36|动态规划Part04|LeetCode:1049. 最后一块石头的重量 II、494. 目标和、474.一和零
目录
LeetCode:1049. 最后一块石头的重量 II
基本思路
C++代码
LeetCode:494. 目标和
基本思路
C++代码
LeetCode:474.一和零
基本思路
C++代码
LeetCode:1049. 最后一块石头的重量 II
力扣代码链接
文字讲解：LeetCode:1049. 最后一块石头的重量 II
视频讲解：动态规划之背包问题，这个背包最多能装多少？
基本思路
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。其中石头的重量为stones[i]，物品的价值也为stones[i]，对应着01背包里的物品重量weight[i]和物品价值value[i]。
- 确定dp数组以及下标的含义
dp[j]的含义，容量为j的背包，最多可以装的价值为 dp[j]。而价值其实也就是背包中能够承载的石头的最大重量。
- 确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);而这里的weight[i]和value[i]实际上都是stone[i]，也就是石头的重量。因此，递推公式可以写成：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
- dp数组如何初始化
既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。根据提示易知，我们要求的target其实只是最大重量的一半，也就是15000。接下来就是如何初始化dp[j]呢，因为重量都不会是负数，所以dp[j]都初始化为0就可以了。
vector<int> dp(15001, 0);- 确定遍历顺序
因为采用的是一维dp数组的方式，因此遍历物品的for循环放在外层而变量背包容量大小的for循环放在内层，并且要保证内层for循环采用倒序遍历。
for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}
}
最后dp[target]就是容量为target的背包所能背的最大重量。在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
C++代码
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(15001, 0);int sum = 0;for (int i = 0; i < stones.size(); i++) sum += stones[i];int target = sum / 2;for (int i = 0; i < stones.size(); i++) { // 遍历物品for (int j = target; j >= stones[i]; j--) { // 遍历背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] - dp[target];}
};LeetCode:494. 目标和
力扣代码链接
文字讲解：LeetCode:494. 目标和
视频讲解：动态规划之背包问题，装满背包有多少种方法？
基本思路
最容易想到的就是回溯算法，但是使用回溯算法容易超时。
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum == target) {result.push_back(path);}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1);sum -= candidates[i];path.pop_back();}}
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (S > sum) return 0; // 此时没有方案if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要格外小心数值溢出的问题int bagSize = (S + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和// 以下为回溯法代码result.clear();path.clear();sort(nums.begin(), nums.end()); // 需要排序backtracking(nums, bagSize, 0, 0);return result.size();}
};
我们如果使用动态规划的方法，可以假设正数的总和为x，负数的总和为y，所有元素的绝对值之和为sum，目标和为target。那么易得：
可以得到：
这里的x实际上就是背包容量BagSize。和之前的方法不同的地方在于，前面的题是求容量为j的背包最多能装下多少。而这个题目是求，装满容量为j的背包，一共有多少种方法。
- 确定dp数组以及下标的含义
dp[j]表示装满容量为j的背包一共有dp[j]种方法。
- 确定递推公式
dp[j] = dp[j] + dp[j-nums[i]],可以理解为不包含物品i为上一次循环中的dp[j]和包含物品i的dp[j-nums[i]]。
- dp数组如何初始化
这里dp[0] 同样初始为1 ,即装满背包为0的方法有一种，放0件物品。并且如果背包容量j和物品0的大小相同，此时dp[nums[i]] = 1。
- 确定遍历顺序
遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）。
C++代码
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> dp(bagSize + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
};LeetCode:474.一和零
力扣代码链接
文字讲解：LeetCode:474.一和零
视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？
基本思路
这个题目依旧是一个01背包问题。但是需要统计每个字符串元素的0和1的数量，也就是两个维度的背包。
- 确定dp数组以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
- 确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
- dp数组如何初始化
01背包的dp数组初始化为0就可以。因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
- 确定遍历顺序
在本题中物品就是strs里的字符串，背包容量是题目描述中的m和n分别代表了dp数组的两个维度。
for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}
}- 举例推导dp数组
以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例
C++代码
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;else oneNum++;}for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};