第九章 动态规划 part04

1049. 最后一块石头的重量 II

本题就和昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。
视频讲解：B站视频
程序员Carl
看着题目感觉很头疼，但是仔细一想，这题很简单，就是很单纯的把两组数分成尽可能相同的值。那这题就和416. 分割等和子集 几乎一模一样了。最后sum-2*dp[target];实际上是（sum-dp[target]）-dp[target]，大的一部分减去小的一部分。遍历过程中尽可能找的是小的一部分。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = std::accumulate(stones.begin(), stones.end(), 0);int target = sum / 2;std::vector<int> dp(target + 1, 0);dp[0] = 0; // 0 可以总是被表示for (int stone : stones) {      for (int j = target; j >= stone; --j) {dp[j]=max(dp[j],dp[j-stone]+stone);}}return sum-2*dp[target];}
};

494. 目标和

大家重点理解递推公式：dp[j] += dp[j - nums[i]]，这个公式后面的提问我们还会用到。
视频讲解：B站视频
程序员Carl
假设加法的总和为x，那么减法对应的总和就是sum - x。

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

此时问题就转化为，用nums装满容量为x的背包，有几种方法。
大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了，例如sum是5，target是2 的话其实就是无解的
同时如果target 的绝对值已经大于sum，那么也是没有方案的。
大家把这张图看懂就没问题了，先确定这个表是什么：先用 二维 dp数组求解本题，dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
装满背包容量为0 的方法个数是1，即 放0件物品。

装满背包容量为1 的方法个数是1，即 放物品0。

装满背包容量为2 的方法个数是0，目前没有办法能装满容量为2的背包。
按照这种顺序一点点的去找规律。dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
dp[i - 1][j]代表不考虑本物体，之前计算出来的装满背包的方法；dp[i - 1][j - nums[i]]代表，不考虑本物体，之前计算出来的装满（背包-本物体重量）的背包的方法；两者相加即可。转换成一维数组也很好理解。因为有用的数据都在上一行，只要保留上一行即可。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = std::accumulate(nums.begin(), nums.end(), 0);if (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bag = (sum-target) / 2;std::vector<int> dp(bag + 1, 0);dp[0] = 1; // 1 可以总是被表示for (int num: nums) {      for (int j = bag; j >= num; --j) {dp[j] += dp[j - num];}}return dp[bag];}
};

474. 一和零

通过这道题目，大家先粗略了解，01背包、完全背包、多重背包的区别，不过不用细扣，因为后面对于完全背包、多重背包还有单独讲解。
视频讲解：B站视频
程序员Carl
这一题本质上是01背包的二维扩展，所以需要先了解01背包的一维写法，就简单很多
只要把这行代码看懂，这题简直超级简单。dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 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 oneNum = 0, zeroNum = 0;for (char c : str) {if (c == '0') zeroNum++;if (c == '1') oneNum++;}for (int i = m; i >= zeroNum; i--) { for (int j = n; j >= oneNum; j--) {dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
};

又干完一个，加油冲冲冲。