1049. 最后一块石头的重量 II
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);for(auto& stone: stones){for(int i=target; i>=stone; i--){dp[i]=max(dp[i],dp[i-stone]+stone);}}return sum-2*dp[target];}
};dp[i]：容量为i的背包所能装载的最大价值（重量）
转移方程：尝试所有可能得石头，它占据空间stone，同时带来价值stone，累计最大。
注意细节：target是向下取整得到，所以是较小的那部分，剩余的部分做被减数。
494. 目标和
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum=accumulate(nums.begin(),nums.end(),0);if((sum-target)%2==1)return 0;if(target>sum)return 0;int negative=(sum-target)/2;vector<int> dp(negative+1,0);dp[0]=1;for(auto& num: nums){for(int i=negative; i>=num; i--){dp[i]+=dp[i-num];}}return dp[negative];}
};假定选择一部分元素形成negative集合，在其之前添加负号满足要求，那么有：
从而可得：
题目转化为，求解和为negative的子集方案数，利用动态规划求解：
dp[i]：和为i的子集方案数
初始化dp[0]=1，表示和为0的方案数为1，即空集：一个都不选也是一种方案。
转移方程：dp[i]+=dp[i-num];
表示dp[i]可由任一个num转移而来，则要求转移前的和为i-num，对应的方案数dp[i-num]，累加所有的可能得到总的方案数。
474. 一和零
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(auto& str: strs){int zero_num=0, one_num=0;for(auto&c :str){if(c=='0')zero_num++;elseone_num++;}for(int i=m; i>=zero_num; i--){for(int j=n; j>=one_num; j--){dp[i][j]=max(dp[i][j],dp[i-zero_num][j-one_num]+1);}}}return dp[m][n];}
};dp[i][j]：0最大i个，1最大j个的最大子集中的元素数目。
转移方程：尝试用所有str刷新“滚动数组”，先统计该str的01分布，使用该str，则dp[i][j]将由dp[i-zero_num][j-one_num]转移而来，累计最大值。
