1049. 最后一块石头的重量 II
1.题目第一次读起来比较抽象,厘清思路发现这不就是把数组分成尽可能相等的两部分吗?这样问题就转化成了我们昨天做地分割等和子集,01背包问题。把数组之和的一半作为背包容量,求出背包最多能装下的石头的重量,剩下一部分与该部分之差就是所求的最后一块石头的重量。(以下代码中数组大小是根据测试用例范围开辟的,事实上只要比target就行)
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
vector<int> dp(1501, 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 - 2 * dp[target];
}
};
2.数组空间优化版
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 - 2 * dp[target];
}
};
494. 目标和
1.回溯法,能做但耗时较长,此处暂时不展开。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum,
int startIndex) {
if (sum == target) {
result.push_back(path);
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex;
i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
if (target > sum)
return 0; // 此时没有方案
if ((target + sum) % 2)
return 0; // 此时没有方案,两个int相加的时候要各位小心数值溢出的问题
int bagSize =
(target + sum) / 2; // 转变为组合总和问题,bagsize就是要求的和
// 以下为回溯法代码
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 需要排序
backtracking(nums, bagSize, 0, 0);
return result.size();
}
};
2.动规,不会,看题解。如何转化为01背包问题呢。假设加法的总和为x,那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = targetx = (target + sum) / 2,此时问题就转化为,装满容量为x的背包,有几种方法。目标值的绝对值比总和大是不行的,目标值与总和加起来为奇数也是不行的。前一个比较好理解,因为题目数组都是非负数,能表示的范围就是总和的相反数到总和,超过了这个范围就表示不出来了。那后一个该如何理解呢?我个人理解的关键在于:偶+偶=偶、偶+奇=奇、奇+奇=偶。举个例子:目标和=加法总和+减法总和,如果目标和是奇数,那么加法总和和减法总和肯定一个是奇数一个是偶数,那么他们俩加起来只能是奇数,即目标和是奇数,总和也只能是奇数。如果目标和是偶数,那么加法总和和减法总和要不是奇奇,要不是偶偶,他们俩加起来一定是偶数,即目标和是偶数,总和也是偶数。综上,目标和与总和奇偶性相同。
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法,递推公式怎么确定呢?例:如果有一个数nums[i],那么就有dp[j - nums[i]]种方法,所以递推公式为:
dp[j] += dp[j - nums[i]]
直接采用一维(滚动)数组,遍历顺序细节不再赘述。
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 ((sum + target) % 2 != 0)
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.一和零
1.本题还是01背包问题的应用,但难度较高。第一次遇到这个题目很难想到背包问题,事实上我已经是第二次看到这个题了,还是没有想到。dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1),该递推公式给我们的启发是+1,状态转移时目标值只会+1,后面我们还会碰到一些题目是类似的思想。至于背包两个for循环都是从后往前,是因为相当于物品重量有两个维度都要满足。该形式已经相当于滚动数组,所以遍历顺序从后往前,防止重复放入物品。
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 zeroNum = 0, oneNum = 0;
for (char a : str) {
if (a == '0')
zeroNum++;
if (a == '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];
}
};
今日总结:菜就多练。