思路：本題石頭是相互粉碎，粉碎后剩下的重量就是兩塊石頭之差，我們可以想到，把石頭分成兩堆總重量分別為A和B，則這兩堆相互粉碎后，剩下的就是這兩堆的重量之差，我們需要使得這個差盡可能小，即把石頭盡可能分為兩部分，使得他們重量差最小。然后和01背包問題對應起來，物品的重量就是石頭的重量stones[i]，物品的價值也是石頭的重量stones[i]，背包的容量最大為重量和除以2，因為這樣使背包盡可能裝滿，二者的差就會最小。dp五部曲：dp數組，dp[j]表示容量為j的背包能裝的最大重量；遞推公式，和之前一樣，當i能裝進去的時候，dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])；dp初始化，首先全部初始化為0，和上題一樣；遍歷順序，對物品從0-i遍歷，但對背包容量需要從大到小遍歷；舉例略。時間復雜度O(mn)，m為總重量。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum=accumulate(stones.begin(),stones.end(),0);int target=sum/2;vector<int> dp(target+1,0);//初始化dp數組for(int i=0;i<stones.size();i++){for(int j=target;j>=0;j--){if(stones[i]<=j){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}}return sum-dp[target]*2;}
};

關鍵在于如何把本題和01背包問題聯系起來。

思路：本題初看就是回溯法的組合總和，但是會超時。然后想想dp的方法，所有數前面只有+和-兩種情況，我們設+的總和為x，則-的總和為sum-x，最后得到x-(sum-x)=2x-sum=target，故x=(sum+target)/2，我們把x當做背包容量，然后把x裝滿即可，需要求的是把容量為x的背包裝滿用的方法數量，其中weight和value都為nums。對x的計算，考慮取整問題，由于2x=sum+target，故sum和target必須奇偶性相同，如果不同則無解，直接排除，還有target的絕對值不可能大于sum，不然也無解，這兩種情況都需要先排除。然后是方案的計算方法，本題也是一個元素只能放一次，故也是01背包問題，但是求解的東西不一樣，01背包求的是最大價值，這里求的是方法數，故我們的dp數組需要有變化。五部曲：dp數組，dp[j]表示容量為j的背包裝滿的最大方法數；遞推公式，還是和之前的方法思考，如果物品i不能最先放進去，那么就沒有新的方法產生，方法數還是原來的dp[j]，如果物品i可以先放進去，那么方法就需要在原有的基礎上增加dp[j-nums[i]]，故dp[j]+=dp[j-nums[i]]；dp初始化，首先如果全部初始化為0，則遞歸后全部都是0，明顯不符合，對于dp[0]，不能初始化為0
只能初始化為1，即背包完全不放，也是一種方法，對其他dp[j]，遞推公式都是從dp[0]慢慢累加起來的，我們初始化為1；遍歷順序，和之前相同；舉例，這種不好想的題目，還是得舉例的，nums=[1,1,1,1,1]，target=3，x=4，dp初始化為[1,0,0,0,0]，當i=0時，dp由遞推公式計算的[1,1,0,0,0]，i=1時，[1,2,1,0,0]，i=2時，[1,3,3,1,0]，i=3時，[1,4,6,4,1]，i=4時，[1,5,10,10,5]，最終答案為5，符合。時間復雜度O(mn)。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=accumulate(nums.begin(),nums.end(),0);if((sum+target)%2==1||abs(target)>sum){return 0;}int x=(sum+target)/2;vector<int> dp(x+1,0);dp[0]=1;for(int i=0;i<nums.size();i++){for(int j=x;j>=0;j--){if(nums[i]<=j){dp[j]+=dp[j-nums[i]];}}}return dp[x];}
};

本題的幾個重點，首先是根據每個元素放一次想到01背包問題，然后是將正負分開計算得出背包容量，這里類似上題的一分為二，只考慮一部分就是背包容量，最后是dp數組的定義，需要根據題目所求靈活設置。
本題的遞推公式dp[j]+=dp[j-nums[i]]常用于求背包中方法數。

思路：本題初看一點想法都沒有，只想到純暴力方法，把所有子集列出來，再計算0和1的個數。直接看解答，首先要弄明白幾種背包問題的區別。

strs里數組的元素就是物品，每個物品只有一個，m和n相當于一個背包，只不過這個背包有兩個維度，即兩個維度都不能超過容量，物品的weight也有兩個維度，分別是0和1的數量，value可以全部認為是1，因為要求集合元素數最大。這里如果按照最初始的01背包問題，需要三維數組，這里我們還是壓縮一維，使用二維數組。五部曲：dp數組，dp[i][j]表示背包中最多物品的數量，其中0的個數不超過i，1的個數不超過j；遞推公式，設物品k中0和1的數量分別為zeroNum和oneNum，則如果物品k能先放進去背包時，dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)；初始化，對dp[0][0]，物品數量為0，我們可以就全部初始化為0，這個和普通的01背包是一個意思；遍歷順序，從背包容量大到小遍歷；舉例略。時間復雜度O(kmn)，k為strs長度。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));//初始化全為0for(int k=0;k<strs.size();k++){int zeroNum=0,oneNum=0;for(char c:strs[k]){if(c=='0'){zeroNum++;}if(c=='1'){oneNum++;}}for(int i=m;i>=0;i--){for(int j=n;j>=0;j--){if(zeroNum<=i&&oneNum<=j){dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);}}}}return dp[m][n];}
};