个人网站如何发布,苏州建站模板厂家,创意网站设计 高端,厦门中标工程信息网学习资料#xff1a;代码随想录
1049.最后一块石头的重量II
力扣题目链接
思路#xff1a;如何讲该问题转化为背包问题#xff1a;还是对半分去碰#xff0c;对半分去碰碰剩下的就是最小的。然后背包容量就是一半儿#xff0c;物品重量等于物品价值等于stones[i]
和上…学习资料代码随想录
1049.最后一块石头的重量II
力扣题目链接
思路如何讲该问题转化为背包问题还是对半分去碰对半分去碰碰剩下的就是最小的。然后背包容量就是一半儿物品重量等于物品价值等于stones[i]
和上一题不同的是return什么这里返回碰完后的值即sum-target-target这里一定不会出现负数以为‘/’是向下取整
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for(int i 0;istones.size();i){sum stones[i];}int target sum /2;vectorint dp(30*100/21,0);for(int i0;istones.size();i){for(int jtarget;jstones[i];j--){ //背包容量看成是和的一半儿,用该容量去碰另一半dp[j] max(dp[j],dp[j-stones[i]]stones[i]);//coutdp[j];}}return (sum-dp[target])-dp[target];}
}; 494.目标和
力扣题目链接
如何将该题转换成背包问题有一个小推导假如分出来的正数是x那么分出来的负数就是-sum-x两数相加等于target就是x-(sum-x) target;
交换一下x (targetsum)/2
求的结果是方法数那么x为背包容量物品的重量等于物品的价值等于nums[i]
定义dp[i][j] 的表示前i个数能够满足选子集可以选0个数求和等于x的方法数量
递推公式dp[i][j]等于不放物品i正好满足j 的方法放i需要把i的容量先让出来正好满足j的方法
初始化第一行当然00处不放是一种方法然后如果物品0能满足背包容量为k的话在0k处方法应该也是1
在左侧第一列需要处理一种特别有意思的情况即物品的重量为0nums[i]0,该物品能够满足背包容量为0的情况。前面有record个num[i] 0的情况那么总的方法会变成2的record次方注意这个方法是会累计的 遇到num[i]0就累积如果遇到num[i]!0,就不累计了但是可别错误得改成1.
遍历顺序第一列已经初始化过了但从0开始遍历也没有问题因为本行是由上一行推导的出的
打印略
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for(int i 0;inums.size();i){sum nums[i];}if((sumtarget)%2!0 || abs(target)sum){ //细节return 0; //你看嗷如果x不是整数不就说明没办法构造吗}int x (targetsum)/2;vectorvectorint dp(nums.size(),vectorint(x1,0));// 第一行if(nums[0]x){dp[0][nums[0]] 1;}// 第一列 int record 0;for(int i0;inums.size();i){if(nums[i]0){record;//coutrecordendl;}//dp[i][0] 2^record; //每一个值为0的数字都有选与不选两种状态dp[i][0] (int) pow(2.0,record);}for(int i1;inums.size();i){for(int j1;jx;j){if(nums[i]j) dp[i][j] dp[i-1][j];else{dp[i][j] dp[i-1][j] dp[i-1][j-nums[i]]; //不放物品i的方法放物品i的方法空出i的值//coutdp[i][j]endl;}} }return dp[nums.size()-1][x];}
};
debug了好久 压缩成一维初始化dp[0]为1就可以了如果第一个物品重量为0的话还可以在递推公式中处理掉
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for(int i 0;inums.size();i){sum nums[i];}if((sumtarget)%2!0 || abs(target)sum){ //细节没有abs在测试用例为nums100target-200时报错return 0; //你看嗷如果x不是整数不就说明没办法构造吗}int x (targetsum)/2;vectorint dp(x1,0);dp[0] 1; //放第一个物品时先把不放物品的这一种情况加上后面递推可以根据nums[0]的值来调整for(int i0;inums.size();i){for(int jx;jnums[i];j--){dp[j] dp[j] dp[j-nums[i]]; //不放物品i的方法放物品i的方法空出i的值//coutdp[i][j]endl;} }return dp[x];}
}; 474.一和零
力扣题目链接
定义dp[i][j]为最多i个0j个1的子集大小
递推公式将每一个strs中的一个字符串看作是一个物品物品重量分别为0的个数和1的个数价值为1代表是子集的一个组成部分
初始化由于value都是1初始化一个小一点的数0就可以了
遍历顺序按一维dp来
打印略
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m1,vectorint(n1,0));for(string str:strs){int zeroNum 0;int oneNum 0;for(char s:str){if (s0) zeroNum;else{oneNum;} //Calculate the weight of every str}for(int im;izeroNum;i--){for(int jn;joneNum;j--){dp[i][j] max(dp[i][j],dp[i-zeroNum][j-oneNum]1); //value[str] 1这句是放与不放str的值的对比}}}return dp[m][n]; }
};
