非常好的学习资料
题目
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
- 1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。 初始的数组的和不会超过 1000 。 保证返回的最终结果能被 32 位整数存下。
关键词
回溯，带备忘录的回溯，动态规划，背包问题
解题
回溯
看这题，第一反应就是回溯。
回溯有个基本框架
int backtrace(vector<int> nums, 选择路径){
if (满足退出条件)
return result;
for (auto 选择: 选择列表){
做选择
backtrace(nums, 选择路径);
撤销选择
}
}
写个基础回溯应该问题不大
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
return backtrack(nums, 0, (long)S, 0);
}
int backtrack(vector<int> &nums, int i, long res, int result){
if (i == nums.size()){
if (res == 0)
result += 1;
return result;
}
result = backtrack(nums, i+1, res+nums[i], result);
result = backtrack(nums, i+1, res-nums[i], result);
return result;
}
};
带备忘录的回溯
这个问题一定有重复子问题，那我把子问题的答案记录下来。这个解法要稍微设计一下，怎么记录子问题。
比较好的方法是用map，信息应该包含：对第i个数做选择，剩下来的数需要凑出来的数值res，有几种凑法。相当于要记三个信息，有点头大！
好消息是 一旦确定 i 和 res，就能获得方案数！即map为string和int的映射表，string包含i和res信息即可。
class Solution {
public:
unordered_map<string, int> memo;
int findTargetSumWays(vector<int>& nums, int S) {
return backtrack(nums, 0, (long)S);
}
int backtrack(vector<int> &nums, int i, long res){
if (i == nums.size()){
if (res == 0)
return 1; //这里需要换，返回的是已明确的方案数
return 0;
}
string key = to_string(i) + '_' + to_string(res); //这里要想一下
if (memo.find(key) != memo.end())
return memo[key];
//result应是所有方案的和
int result = backtrack(nums, i+1, res+nums[i]) + backtrack(nums, i+1, res-nums[i]);
memo[key] = result;
return result;
}
};
背包&动态规划
我的数学思维能力需要专项训练的样子，目前还不行
A: 所有采用+的数的集合，B：所有采用-的数的集合
sum(A) - sum(B) = S
sum(A) + sum(A) = S + sum(B) + sum(A)
sum(A) = (S + sum)/2
小可爱发现什么了！没有错，问题变成了 从整体集合中挑选数，使它们的和为一个常数，有多少种方案。
典型的背包问题了，用动态规划来解。
动态规划三步走：确定定义，写状态转移函数，写base case。
-
确定定义
dp[i][j]：前i个数中任意挑选，和为j的有多少种方案
-
状态转移：
dp[i][j] = dp[i-1][j] (不放第i个数的方案数）+ dp[i-1][j-第i个数]（放第i个数的方案数）
-
base case：
dp[:][0] = 1
写代码的时候有个问题
我的i表示前i个数里挑选，i=0的时候表示没有数的时候
而nums里的第i个数下标是i-1
因此，正确的状态转移方程是：
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
我花时间比较多的点在于，我错误写成了如下：
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
明确这些了来写代码
class Solution {
public:
/*
A: 所有采用+的数的集合，B：所有采用-的数的集合
sum(A) - sum(B) = S
sum(A) + sum(A) = S + sum(B) + sum(A)
sum(A) = (S + sum)/2
*/
int findTargetSumWays(vector<int>& nums, int S) {
long sum = 0;
for(auto x:nums) sum+=x;
if (S > sum || (sum + S)%2!=0) return 0;
int target = (sum + S)/2;
return subset(nums, target);
}
int subset(vector<int>& nums, int target){
//背包问题
//dp[i][j]: 在前i个数中选择恰好装满背包j有几种方法
//dp[nums.size()-1][target]是结果
//dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] 第i个物品不装的方案个数：dp[i-1][j]，第i个物品装的方案个数：dp[i-1][j-nums[i-1]]
//初始化
int size = nums.size();
vector<vector<int>> dp(size+1, vector<int>(target+1, 0));
for(int i = 0; i <= size; i++) dp[i][0] = 1;
for(int i = 1; i <= size; i++){
for(int j = 0; j <= target; j++){
if (j-nums[i-1]>=0)
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
else
dp[i][j] = dp[i-1][j];
}
}
return dp[nums.size()][target];
}
};
动态规划的维度压缩
是的，没有错！
可以看出，每个dp[i]仅依赖于dp[i-1]，那这就是可以做路径压缩的呀小可爱们
道理是这样：即然我要更新dp[i]，只需要dp[i-1]的信息，那我就可以无脑删掉关于[i]的下标，使用一维数组实现维度压缩
这个时候状态议程变成了：
dp[j] = dp[j] + dp[j-nums[i-1]]
为了保证我每次迭代的时候，dp[j]和dp[j-nums[i-1]]都是上一轮的值，j需要从后往前更新。即我更新dp[j]时，dp[j-nums[i-1]]是i-1轮的值，而非第i轮的值，那j只能从大往小走了，要从小往大走的话，上一轮的dp[j-nums[i-1]]就没了
道理理清了，来写代码
class Solution {
public:
/*
A: 所有采用+的数的集合，B：所有采用-的数的集合
sum(A) - sum(B) = S
sum(A) + sum(A) = S + sum(B) + sum(A)
sum(A) = (S + sum)/2
*/
int findTargetSumWays(vector<int>& nums, int S) {
long sum = 0;
for(auto x:nums) sum+=x;
if (S > sum || (sum + S)%2!=0) return 0;
int target = (sum + S)/2;
return subset(nums, target);
}
int subset(vector<int>& nums, int target){
//背包问题
//dp[i][j]: 在前i个数中选择恰好装满背包j有几种方法
//dp[nums.size()-1][target]是结果
//dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] 第i个物品不装的方案个数：dp[i-1][j]，第i个物品装的方案个数：dp[i-1][j-nums[i-1]]
//初始化
int size = nums.size();
vector<int> dp(target+1, 0);
for(int i = 0; i <= size; i++) dp[0] = 1;
for(int i = 1; i <= size; i++){
for(int j = target; j >=0; j--){
if (j-nums[i-1]>=0)
dp[j] = dp[j] + dp[j-nums[i-1]];
else
dp[j] = dp[j];
}
}
return dp[target];
}
};
