动态规划理论基础
动规五部曲：
- 确定dp数组 下标及dp[i] 的含义。
- 递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
- 初始化dp数组。
- 确定遍历顺序：从前到后or其他。
- 打印。
出现结果不正确：
- 打印dp日志和自己想的一样：递推公式、初始化或者遍历顺序出错。
- 打印dp日志和自己想的不一样：代码实现细节出现问题。
1049. 最后一块石头的重量 II
参考文档：代码随想录
题目：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
- 示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。- 提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
分析：
刚开始解题出现了误区，对stone从小到大的排列，偶数相邻元素之间抵消成新的值，奇数最大和最小抵消形成新的值后转为偶数的计算。一轮计算之后重复计算直到集合只剩一个元素。这个思路是重复的排列和相邻的抵消。这就不属于动态规划了，在动态规划中，将整个集合抽象为两个集合，集合1是抵消的集合，集合2是被抵消的集合。集合1-集合2就是最后的结果，要想（集合1-集合2）最小，就要使两个集合最接近，这就想到结合的和 sum/2，集合中是否存在子集和是最接近 sum/2 的，这个子集和就是所求的集合2。问题转为13.分割子集和的问题。
代码：文章来源地址https://www.toymoban.com/news/detail-835196.html
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0, target = 0;
for(int i = 0; i < stones.size(); i++){
sum += stones[i];
}
target = sum/2;
vector<int> dp(target+1, 0);
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]);
}
}
sum = sum - dp[target] - dp[target];
return sum;
}
};
494. 目标和
参考文档：代码随想录
分析：
正整数集合分成两个正整数的集合，left与right，一个是正数，一个是即将加负号的负数。有left-right=target; left + right = sum; 推出left = (target+sum)/2; 所有只要找到总集合中相加为left的方法个数就可以得到答案。问题转为集合划分为子集和，求实现子集和的方法数。所以是组合问题，递推公式为dp[i] = dp[i] + dp[i-nums[i]]; dp[i]表示实现i原来的方法数，dp[i-nums[i]]表示不加nums[i]的最多方法数，这个集合加入nums[i]就会得到 i。初始化时候的dp[0]应该设为1，这样不会导致之后的相加一直是0，可以理解为集合和为0有一种方法就是全部都为0。其余位置的初始化为0。
代码：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//分析：两个正数集合left、right，left-right=target，left+right=sum,left=(sum+target)/2
//接下来计算到left的集合的方法数，另一个就是right
//dp[i]含义：集合和为i的方法个数
//递推公式：dp[i] = dp[i] + dp[i-nums[i]];
//初始化：dp[0] = 1,其余为0
//遍历顺序：0-1背包
int sum = 0, left = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
}
if((sum+target)%2 == 1) return 0;
if((sum + target) < 0) return 0;
left = (sum+target) / 2;
//初始化
vector<int> dp(left+1, 0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++){
for(int j = left; j >= nums[i]; j--){
dp[j] = dp[j] + dp[j-nums[i]];
}
}
return dp[left];
}
};
474.一和零
参考文档：代码随想录
分析：
dp[i][j]含义是i个0，j个1的集合中最大的字符串个数。
进而递推公式是dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1); 所以本题和0-1背包的滚动数组是类似的，只不过在是否放入背包的条件中不仅有0的限制还有1的限制，这表明在背包的循环体中处理的背包由一维上升到了二维。
在遍历顺序上，必须先物品再背包，在物品的循环体中需要计算出该物品中0的个数和1的个数，在背包中，需要判断该不该把这个物品放入容量为i个0，j个1的背包中。在背包的遍历顺序中，应该和滚动数组的行为保持一致，需要倒序。
在初始化中，有一点干扰到了我，我将0-1背包的二维初始化和这个背包的二维初始化联系起来，所以思考怎么初始化行、初始化列，但是这个联系就是错误的，dp[i][j]的含义是i个0，j个1的背包可以容纳的最多个数的字符串个数，所以dp数组中每个位置的初始化应该由之后背包的遍历中确定，刚开始的初始化和滚动数组的初始化一直，全部设为0。文章来源：https://www.toymoban.com/news/detail-835196.html
代码：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
//题目分析为有两个维度的背包，一个是m，另一个是n
//dp[i][j]：有i个0，j个1的集合的最大长度。（！！！）
//递推公式：dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1);
//初始化：全0
//遍历顺序：先物品再背包，因为先物品需要计算出二进制字符串中0和1的个数
int zeroNum = 0, oneNum = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for(int i = 0; i < strs.size(); i++){
zeroNum = 0, oneNum = 0;
for(char c : strs[i]){
if(c == '0') zeroNum++;
else oneNum++;
}
for(int j = m; j >= zeroNum; j--){
for(int k = n; k >= oneNum; k--){
dp[j][k] = max(dp[j][k], dp[j-zeroNum][k-oneNum]+1);
}
}
}
return dp[m][n];
}
};
到了这里，关于【Day43】代码随想录之动态规划0-1背包_1049. 最后一块石头的重量 II_494. 目标和_ 474.一和零的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
