1049. 最后一块石头的重量 II
思路：
这道题的思路和第416题是一致的，可以把石头分成重量相近的两堆然后相撞，这样的剩余重量是最小的。由此可将问题转换成一个容量为sum/2的背包能装的最大价值问题。dp[i]：容量为i的背包能装的最大价值为dp[i]；初始化：dp[0]=0；递推关系：dp[i]=max(dp[i],dp[i-weight[i]]+weight[i])；遍历顺序：先遍历物品，后遍历背包，背包逆序遍历。
代码：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(1501,0);
int sum=0;
for(int i=0;i<stones.size();i++)
{
sum+=stones[i];
}
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])-dp[target];
}
};
494. 目标和
思路：
这道题可以转化为两个正数right、left，两个数做差为target，两个数的和为sum，求解容量为left的背包有多少种装法。dp[i]：容量为i的背包有dp[i]种装法，初始化：dp[0]=1，递推关系：dp[i]可以分解成1+dp[i-1]、2+dp[i-2]......，遍历顺序：先物品后背包，背包倒序遍历。
代码：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if (abs(target) > sum) return 0;
if ((target + sum) % 2 == 1) return 0;
int left=(sum+target)/2;
vector<int> dp(10001,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];
}
};
474. 一和零
思路：
这道题目可以看成是一个二维的背包问题，每个字串可以看成物品，物品的重量是二维的，即每个字串中0的个数和1的个数。dp[i][j]：有i个0，j个1的背包能装的最多字串为dp[i][j]。初始化：dp[0][0]=0。递推关系：针对某一个物品，不装入背包时能装的最多字串是dp[i][j]，如果装入背包时，能装的最多字串是dp[i-x][j-y]+1，x表示该物品中0的个数，y表示该物品中1的个数。将两者情况取最大值就能得到递推关系。遍历顺序：先遍历物品，后遍历背包，背包从后向前遍历。
代码：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(string str:strs)
{
int x=0,y=0;
for(char p:str)
{
if(p=='0')
{
x++;
}else
{
y++;
}
}
for(int i=m;i>=x;i--)
{
for(int j=n;j>=y;j--)
{
dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
}
}
}
return dp[m][n];
}
};
