本文主要是介绍【Day43】代码随想录之动态规划0-1背包_1049. 最后一块石头的重量 II_494. 目标和_ 474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 动态规划理论基础
- 动规五部曲:
- 出现结果不正确:
- 1049. 最后一块石头的重量 II
- 494. 目标和
- 474.一和零
动态规划理论基础
动规五部曲:
- 确定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.分割子集和的问题。
代码:
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。
代码:
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.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!