[leetcode]494. 目标和

非常好的学习资料

题目

链接

给定一个非负整数数组，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];
    }
};