416. 分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {vector<int> dp(10001,0);int sum=accumulate(nums.begin(),nums.end(),0);if(sum%2) return false;int target=sum/2;for(int i=0;i<nums.size();i++){for(int j=target;j>=nums[i];j--){dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[target]==target) return true;return false;}
};

這道題可以用回溯做，也可以用01背包做，題目要求是分出兩個子集和相等，這道題背包容量就是sum/2，物品個數就是nums.size()，物品重量就是物品自己，物品價值也是物品自己，所以遞推公式為dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])

1049.最后一塊石頭的重量II

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(1501,0);int sum=accumulate(stones.begin(),stones.end(),0);int target=sum/2;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 sum-dp[target]*2;}
};

這道題和上一題類似，求出兩兩粉碎后，剩下最小的石頭，其實就是上一題的變種，看是否分成兩堆的石頭能相互抵消，如能抵消就是返回0，如果抵消不了就是接近dp[target]的兩堆石頭相減（sum-dp[target]-dp[target]）

494.目標和

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=accumulate(nums.begin(),nums.end(),0);if(abs(target)>sum) return 0;if((target+sum)%2) return 0;int bagsize=(target+sum)>>1;vector<int> dp(sum+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];}
};

轉化為背包問題思路，求目標和，就是把數組分為整數一組，負數一組（即將被賦予負號的子集），求目標和其實就是正數組減去負數組，正數組我們令為left，負數組令為right，所以根據公式推導，left+right=sum,left-right=target.所以left=（sum+target）/2,所以bagsize就為（sum+target）/2，dp[j]的含義為背包容量為j時最多有多少種方法，和爬樓梯類似，遞推公式為

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