代码随想录算法训练营第四十三天|1049. 最后一块石头的重量

1049. 最后一块石头的重量 II 

关键将一堆石头分成两份，近可能接近平均值

动规五步曲：

确定dp数组以及下标的含义

dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]

确定递推公式

dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

dp数组初始化

dp数组开到15000

vector<int> dp(15001, 0);

确定遍历顺序

for(inti=0;i<stones.size();i++){// 遍历物品for(intj=target;j>=stones[i];j--){// 遍历背包dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}

494. 目标和

在集合nums中找出和为left的组合

问题就转化为，装满容量为x的背包，有几种方法

定dp数组以及下标的含义

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

确定递推公式

dp[j] += dp[j - nums[i]]

dp数组如何初始化

dp[0] =1

确定遍历顺序

nums放在外循环，target在内循环，且内循环倒序

intfindTargetSumWays(vector<int>&nums,intS){intsum=0;for(inti=0;i<nums.size();i++)sum+=nums[i];if(abs(S)>sum)return0;// 此时没有方案if((S+sum)%2==1)return0;// 此时没有方案intbagSize=(S+sum)/2;vector<int>dp(bagSize+1,0);dp[0]=1;for(inti=0;i<nums.size();i++){for(intj=bagSize;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}returndp[bagSize];}

474.一和零  

动规五部曲：

确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1

在遍历的过程中，取dp[i][j]的最大值

dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)

dp数组如何初始化

dp数组初始化为0

确定遍历顺序

外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历

for(string str:strs){// 遍历物品intoneNum=0,zeroNum=0;for(charc:str){if(c=='0')zeroNum++;elseoneNum++;}for(inti=m;i>=zeroNum;i--){// 遍历背包容量且从后向前遍历！for(intj=n;j>=oneNum;j--){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}