阿里巴巴国际网站建设,百度校招,零基础自学python,淮安市淮阴区建设局网站416.分割等和子集
分析#xff1a;需要总和能分成两半#xff0c;并且有子集能装满一半
思路#xff1a;
1.dp存储#xff1a;容量为j时装入的最大数值和dp[j]2.dp[j]max(dp[j],dp[j-nums[i]]nums[i]) 3.全部初始化为04.遍历顺序#xff1a;外层遍历元素#xff0c;内…416.分割等和子集
分析需要总和能分成两半并且有子集能装满一半
思路
1.dp存储容量为j时装入的最大数值和dp[j]2.dp[j]max(dp[j],dp[j-nums[i]]nums[i]) 3.全部初始化为04.遍历顺序外层遍历元素内层遍历重量
2 dp[j]就是上一轮还没有遍历到当前nums[i]时的最大和所以相当于不装nums[j] dp[j-nums[i]]为啥要 j-nums[i] 的容量呢因为要满足容量为 j 所以装之前要找到 容量为 j-nums[i] 装入的最大和然后装入当前 nums[i] 总容量才为 j 要是直接dp[j]nums[i]就会导致容量超过 j 。 1049.最后一块石头的重量 ||
分析石头相撞剩余多出的部分相当于能分成的最近似的两堆石头
思路
1.dp存储先将stones总和求出求出一半dp存储的是容量为 j 装的最大重量2.dp[j]max(dp[j],dp[j-stones[i]]-stones[i]);3.初始化全部初始化为04.遍历顺序外层遍历石头内层遍历容量
class Solution {
public:int lastStoneWeightII(vectorint stones) {int total0;for(auto it:stones) totalit;int targettotal/2;vectorintdp(total1,0);for(int i0;istones.size();i){for(int jtarget;jstones[i];j--){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}return total-dp[target]*2;//装入的最大重量跟剩下的相抵消剩余的就是最后一块石头}
}; 494.目标和一刷坐牢
分析正数总和-负数总和目标和 - 正数总和目标和总和/2
思路
1.dp存储当和容量为 j 时有dp [ j ] 中装法 。2.dp[ j ] dp [ j - nums [ i ] ] ;3.初始化dp [ 0 ] 1 ;4.遍历顺序外层遍历数组内层遍历容量
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum0;for(int it:nums) sumit;if(abs(target)sum) return 0;//当总和小于目标和的绝对值时不可能有情况因为target被抵消过//add表示正数的总和sub表示负数的总和//add-(sum-add)target//add(targetsum)/2if((targetsum)%21) return 0;int bagSize(targetsum)/2;vectorint dp(bagSize1,0);dp[0]1;for(int i0;inums.size();i){for(int jbagSize;jnums[i];j--)dp[j]dp[j-nums[i]];}return dp[bagSize];}
}; 474.一和零坐牢
分析这一题还是背包不同是有物品有两个维度 0 和 1
思路
1.dp存储当 0 容量为 i 1 容量为 j 时最多能装dp [ i ][ j ] 个字符串2.dp [ j ]dp [ i ] [ j ] max( dp [ i ] [ j ] , dp [ i - zeroNum ][ j - oneNum ] 1 ] 3.初始化全部初始化为04.遍历顺序外层遍历字符串数组内层进行两个循环遍历
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorintdp(m1,vectorint(n1,0));for(string str:strs){int oneNum0,zeroNum0;for(char c:str){if(c0) zeroNum;else oneNum;}for(int im;izeroNum;i--){for(int jn;joneNum;j--){dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1);}}}return dp[m][n];}
};
