day-42 代码随想录算法训练营 动态规划 part 04

416.分割等和子集

分析：需要总和能分成两半，并且有子集能装满一半

思路：

• 1.dp存储：容量为j时装入的最大数值和dp[j]
• 2.dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])  
• 3.全部初始化为0
• 4.遍历顺序：外层遍历元素，内层遍历重量

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.初始化：全部初始化为0
• 4.遍历顺序：外层遍历石头，内层遍历容量

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int total=0;for(auto it:stones) total+=it;int target=total/2;vector<int>dp(total+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]);}}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(vector<int>& nums, int target) {int sum=0;for(int it:nums) sum+=it;if(abs(target)>sum) return 0;//当总和小于目标和的绝对值时，不可能有情况（因为target被抵消过）//add表示正数的总和，sub表示负数的总和//add-(sum-add)=target//add=(target+sum)/2if((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];}
};

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.初始化：全部初始化为0
• 4.遍历顺序：外层遍历字符串数组，内层进行两个循环遍历

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>dp(m+1,vector<int>(n+1,0));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);}}}return dp[m][n];}
};