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);}}}
网友评论