1049.最后一块石头的重量II
题目链接：1049.最后一块石头的重量II
文档讲解：代码随想录
状态：不会，不知道如何转化
思路
01背包衍生题目主要思路：在商品中取，使得容量有限的背包价值最大或取法数量、或元素数量最大等。
本题简单思路为将数组石头分成最相近两组（sum/2）,此时做差最小。正确性就不证明了，囫囵吞枣吧，头受不了了。
此时的背包问题为：在容量为sum/2的背包中装填，石头的体积与价值相同（关键理解这是一个存在性+最优问题），则最终的dp[target]为最优。
题解
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0, target = 0;
for(auto &i:stones)sum += i;
target = sum/2;
vector<int> dp(sum+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];//注意这个点，失误过很多次
}
};
494.目标和
思路
01背包衍生题目主要思路：在商品中取，使得容量有限的背包价值最大或取法数量、或元素数量最大等。
本题知道了是找容量和为bagsize的组合数：此时的nums数组内容为所占体积，所求不是价值，递推公式需要进行修改。
对于组合数的递推公式类似于爬楼梯：①如果j<nums[i]，此时放不下，不需要更改；②如果j>=nums[i]，此时可以放下，需要增加新情况，注意不是赋值！！！dp[j] += dp[j - nums[i]]
题解
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(auto &i:nums)sum += i;
if((sum+target)%2!=0)return 0;
if (abs(target) > sum) return 0; // 此时没有方案,因为不能是负数
int bagsize = (sum+target)/2;
vector<int> dp(bagsize+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];
}
};
474.一和零
思路
01背包衍生题目主要思路：在商品中取，使得容量有限的背包价值最大或取法数量、或元素数量最大等。
背包容量是m、n多一个维度，但是做法一样，关键点在于所求值为背包内元素数量->仅仅把价值改为1即可。
还要注意本题本应是dp[i][j][k]，简化为二维数组，遍历时由滚动性，顺序极其重要！！！
题解
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, y = 0;
for(auto &i:strs[i]){if(i == '0')x++;else if(i == '1')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];
}
};
动态规划好似浑然天成，让我想破了脑子