- y总题解,LauZyHou,wzc1995
-
题目类型:
在给定集合中,判断是否存在 和为定值 的组合 或者 求 和为定值的组合的数量。
- 相似题目:转化为01背包问题后,类似于 lc 416. 分割等和子集
题目
思路
1. 二维写法(类似于01背包)
1.1 y总二维:y总题解
//160 ms, 44.39%; 38.7 MB,7.40%
// y总讲解 二维解法:其中 f[i][j]中j的范围,设置为了[0, 2 * Offset]
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
// 由于题目里说数组里总和最多只有1000,所以只能做[-1000,+1000],如果S不在这个范围就直接返回
if (abs(S) > 1000) return 0; // S < -1000 || S > 1000
int n = nums.size(), Offset = 1000; // 因为有负数,所以这里用一个偏移量,所有的j放到f里都要加上这个偏移量
vector<vector<int>> f(n + 1, vector<int>(2 * Offset + 1));
f[0][0 + Offset] = 1; // 选0个数,总和也是0的情况(因为在f数组里所以加上了一个偏移量Offset)
for (int i = 1; i <= n; i ++ ) {
// 本来 j范围是[-Offset, Offset],加上偏移量之后变为[-Offset + Offset, Offset + Offset], 即[0, 2* Offset]
for (int j = 0; j <= 2 * Offset; j ++ ) { // f[i][j] 第二维下标 的范围要在 [0, 2*Offset] 之内
// 注意:因为nums的下标是从0开始的,所以这里要用nums[i - 1]
// a[i]取正数,0 <= j - nums[i - 1] <= 2*Offset, 因为 j~[0, 2*Offset]且nums[i]非负,所以肯定满足右半边不等式
if (j - nums[i - 1] >= 0) // 只约束左半边不等式即可
f[i][j] += f[i - 1][j - nums[i - 1]];
// a[i]取负数,0 <= j + nums[i - 1] <= 2*Offset, 因为 j~[0, 2*Offset]且nums[i]非负,所以肯定满足 左半边不等式
if (j + nums[i - 1] <= 2 * Offset) // 只约束右半边不等式即可
f[i][j] += f[i - 1][j + nums[i - 1]];
}
}
return f[n][S + Offset]; // 在前n个数里选,总和是S的方案数
}
};
- 之所以优化不成 01背包问题的一维写法,是因为 j 的 for循环里面 有两个 if:
- if (j - nums[i - 1] >= 0) $f[i][j] += f[i - 1][j - nums[i - 1]];$ 这里要优化成一维,j 的for循环
只能逆序更新
。 - if (j + nums[i - 1] <= 2 * Offset) $f[i][j] += f[i - 1][j + nums[i - 1]];$ 这里要优化成一维,j 的for循环
只能正序更新
。 正序更新
和逆序更新
发生了矛盾
,所以不能
优化成 基本的01问题模板 的 一维写法。
- if (j - nums[i - 1] >= 0) $f[i][j] += f[i - 1][j - nums[i - 1]];$ 这里要优化成一维,j 的for循环
1.2 y总二维 空间优化, wzc1995:
- 这里的优化 不是 指优化成 一维,只是将边界范围 减小。
// 124 ms, 45.40%; 22.1 MB, 12.51%
// 对y总讲解 二维解法 进行空间优化:其中 f[i][j]中j的范围,从 [0, 2 * Offset] 设置成 [0, 2 * sum]
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
if (abs(S) > sum) return 0;
vector<vector<int>> f(n + 1, vector<int>(2 * sum + 1, 0));
f[0][0 + sum] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= 2 * sum; j++) { // j~[-sum, sum] 加偏移量sum之后-->j~[0, 2 * sum]
if (j - nums[i - 1] >= 0) // nums的下标是从0开始的,要用nums[i - 1]
f[i][j] += f[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] <= 2 * sum)
f[i][j] += f[i - 1][j + nums[i - 1]];
}
return f[n][S + sum];
}
};
2. 一维写法(转变为 最基本的01背包)
- 力扣官方
- 转化为
最基本的01背包问题
的关键:- 设 所有整数和为sum, 添加负号的整数的和 为 neg, 添加正号的整数的和为 sum - neg, target = (sum - neg) - neg, 由等式可以推出 neg = (sum - target) / 2。这样就转化为
给定集合,找和为neg = (sum - target) / 2 的组合的数量
的 最基本的01背包问题。 - 注意: 题目中nums[i] 均为非负整数,neg = (sum - target) / 2 为非负整数, 所以如果 sum - target 为 负数 或 奇数 的话,就无解
- 设 所有整数和为sum, 添加负号的整数的和 为 neg, 添加正号的整数的和为 sum - neg, target = (sum - neg) - neg, 由等式可以推出 neg = (sum - target) / 2。这样就转化为
- 之所以能转化为 一维写法的
关键原因
:问题转化为在给定集合中 找到 和为 固定值(target-sum)/2 的 组合的数量
后,对集合中的每个元素 只有 选 或 不选 两种选择,这样就相当于最基本的01背包问题,如果采用二维dp数组$f[i][j]$,那么 j 的for循环里面只有一个 if
,此时就可以 根据情况 将for循环 选择 逆序 或 正序 更新,即可转化为一维写法。 - 题目类型:
在给定集合中,判断是否存在 和为定值 的组合 或者 求 和为定值的组合的数量。
- lc 416. 分割等和子集 是
判断 在 给定集合中 能否找到 和为 固定值sum/2 的组合
,即判断是否存在符合条件的组合
。 - 本题 lc 494. 目标和, 相当于
在给定集合中 找到 和为 固定值(sum - target)/2 的 组合的数量
。即找出符合条件的组合的数量
。
- lc 416. 分割等和子集 是
// 0 ms, 100.00%; 9.2 MB, 33.14%
// 转化为01背包问题, 在给定集合中 找到 和为 固定值(sum - target)/2 的 组合的数量
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0, n = nums.size();
for (auto& x : nums) sum += x;
int diff = sum - target;
if ((diff < 0) || (diff & 1)) return 0; // diff 是否为负数 或 奇数
int neg = diff / 2; // neg 为所有 添加负号的 整数的和
vector<int> f(neg + 1);
f[0] = 1;
for (auto& x : nums)
for (int j = neg; j >= x; j -- )
f[j] = f[j] + f[j - x];
return f[neg];
}
};
给大佬点赞
声明一个全局count就OK
赞,不过
一维DP
的时间复杂度 低一点。-
回溯
的 时间复杂度 是 O(2^n
),递归栈空间 O(n
);-
一维 DP
的时间复杂度 是 O(n * (sum - target)
),空间是 O(neg
)。恩,主要是懒,才这样写,哈哈。
hh 一起加油~ 冲冲冲
完全一样,勉强能过