代码随想录算法训练营第31天 | 第九章动态规划 part04
第九章 动态规划 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];
}
};
又干完一个，加油冲冲冲。
原文地址：https://blog.csdn.net/zxjiaya/article/details/142731409
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！