算法思想：
可以转化为0-1背包问题。其实就是把石头分成基本上相等的两堆，相撞，差值就是剩下的石头。背包容量为石头重量总数的一半, 就是找到尽可能接近到sum/2的石头。我们的目标重量为sum/2的值
石头的重量等价于0-1背包中的价值和重量。
最后
则有递推公式：
dp[j] = max(dp[j], dp[j- stones[i]] + stones[i])
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for(int i=0;i<stones.size();i++)
{
sum += stones[i];
}
int target = sum/2;
vector<int> dp(target+1, 0);
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] - dp[target];
// sum - dp[target] 表示第一堆的重量；dp[target]表示第二堆的重量
}
};
算法思想：
0-1背包问题。对于每个数选或者不选它给它加上符号+
其实就是分成两堆，一堆符号位+，一堆符号位-。
假设符号为+的用left表示，符号为-的用right表示。
left + right = sum
left - right = target;
left-target = right
left + left-target = sum
left = (sum + target)/2
就是寻找有多少种组合，和为left。
dp[j] 表示有dp[j]中组合，和为j
递推公式：
dp[j] = dp[j-nums[0]] + dp[j-nums[1]] + .... + dp[j]
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(int i=0; i <nums.size();i++)
sum += nums[i];
int left = (sum + target) /2;
if(abs(target)>sum)
return 0;
if((sum + target) %2==1)
return 0;
vector<int> dp(left+1, 0);
dp[0] = 1;
for(int i=0;i<nums.size();i++)
{
for(int j=left;j>=nums[i]; j--)
{
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
}
};
算法思想：
本质上是0-1背包问题。这个物品取或者不取。
但是这个背包容量有两个维度，m和n。那么对应的物品也有两个维度的重量x，和y表示0和1的数量
递推公式：
dp[m][n] = max(dp[m-x][n-y], dp[m][n])
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int> (n+1, 0));
for(int i=0;i<strs.size();i++) //遍历物品
{
int x=0;
int y=0;
for(int k1 = 0;k1<strs[i].size();k1++)
{
if(strs[i][k1]=='0')
x++;
else
y++;
}
for(int j1=m;j1>=x;j1--)
{
for(int j2=n;j2>=y;j2--)
{
dp[j1][j2] = max(dp[j1][j2], dp[j1-x][j2-y]+1);
}
}
}
return dp[m][n];
}
};
