494.目标和

2020-05-10

题目

1
2
3

>给定一个非负整数数组，`a1, a2, ..., an`, 和一个目标数，`S`。现在你有两个符号 `+ `和` -`。对于数组中的任意一个整数，你都可以从 `+` 或` -`中选择一个符号添加在前面。

>返回可以使最终数组和为目标数 `S` 的所有添加符号的方法数。

示例 1:

>输入: 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位整数存下。

1
2
3

>来源：力扣（LeetCode）
>链接：https://leetcode-cn.com/problems/target-sum
>著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目的要求是求一个对结果有限制条件的方法总数，在题目要求上类似的问题是 小青蛙跳台阶问题，用递归解决；
输入非负整数数组大小为N，那么所有可能的组合有 $2^n$ 种，需要遍历所有的组合来得到所有满足条件的方法；

实现

递归实现：

求N个数的加减得到S和方法数，可以递归地求选定第n个值的符号之后，剩下N-1个数字加减得到更新后的S的方法数，对当前第n个值的两种可能取值求和；
因为这个问题比较简单，我们这里只关注递归的终止条件：输入数组为空；
然而我们注意到输入参数的大小是与N相关的，递归 $N$ 次，那么空间复杂度为 $O(N^2)$ ，随后注意到题目限制了输入数组的大小不超过20求非空，因此这里不需要考虑空间复杂度；

然而我们可以写一个辅助函数，把输入输出引用换成Solution类的数组成员的迭代器，这样可以在不限制输入数组大小的前提下避免栈溢出，空间复杂度 $O(N)$ ；

然而果然还是超时了…代码如下：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        input.assign(nums.cbegin(), nums.cend());
        return helper(input.cbegin(), S);
    }
private:
    vector<int> input;
    int helper(decltype(input.cbegin()) it, int S){
        if(it == input.cend() && S == 0) return 1;
        else if(it == input.cend() && S != 0) return 0;
        return helper(it+1, S+*it) + helper(it+1, S-*it);
    }
};

时间复杂度为所有可能的结果 $O(2^N)$ ，是算法绝对不可接受的时间复杂度。

动态规划

之前已经总结过动态规划（0-1背包问题），这里只针对题目进行分析。

如何将问题转化为0-1背包问题进行求解是难点。在0-1背包中，针对每一个元素（物品），都是一个选或不选的问题，通过比较选与不选，相应背包的价值来决定每一个元素的取舍。

而在本题中，针对每一个元素，我们无法决定是取正号还是取负号，因为我们无法知道取正号或取符号是否能使整个序列的和满足条件。因此我们需要转换问题，使其成为一个可以动态规划（每一次做决定都可以根据设定的优化目标进行规划）的问题。与其思考针对一个元素应该取什么符号，我么不如把元素符号先定下来，假设他是正号，那么我要不要取这个元素。也就是说，整个集合加上符号之后分为两个子集：非负子集和负数子集，我们对每一个元素，要决定是否把他加入其中的某一个子集，我们这里就考虑是否将它加入非负子集中。

假设 $S(X)$ 表示对一个集合中的所有元素进行求和的函数，那么当我们把输入的非负整数集合 $Q$ 划分为加正号的集和 $P$ 和加负号的集和 $N$ ，此时将限制条件 $S(P)-S(N)=S$ 转化为 $S(P)=S(N)+S$ ，这样，对于每个元素，我们在已经知道 $S(P)$ 的前提下，如果也知道 $S(N)$ ，就可以进行动态规划了！而已知 $S(P)$ 和 $Q$ ，很容易就可以求得 $S(N)=S(Q)-S(P)$ ，可以化为 $2S(P)=S(Q)+S$ ，三个量我们都知道的情况下，就可以根据新的限制条件进行动态规划，决定当前元素的符号，从而转化为了0-1背包问题。

下面放上以上分析和思考所参考题解的代码进行分析：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = 0; // S(Q)
        for (const int &it : nums) sum += it; // 求S(Q)
        if ((S + sum) % 2 == 1 || S > sum) return 0; // 算法的优化，排除一定不存在解的情况：S(Q)+S不能被2整除 或 目标和S超出S(Q)值域
        S = (S + sum) / 2; // 计算S(P)
        int *dp = new int[S + 1]; // dp[s]为目标和S=s的方法数，我们要求的就是dp[S]，由于已经知道S(P)，那么背包容量为S(P)，至此彻底化为0-1背包问题
        memset(dp, 0, (S + 1) * sizeof(int));
        dp[0] = 1; // 注意dp的下标S的含义已经变成集合P的目标和，如果集合P的目标和为0，那么只有一种选法，就是什么都不选
        for (const int &it : nums) { // 对Q中每个元素
            for (int j = S; j >= it; j--) // j为当前剩余所需目标和，若当前元素大于j，那么跳过该元素，求解可能选择当前元素的所有剩余目标和的方法数
                dp[j] += dp[j - it]; // 写成dp[j] = dp[j]+dp[j-it]更容易理解，实际上就是目标和为j的方法数为：将该元素加入P的方法数+不将该元素加入P的方法数
        }
        int ans = dp[S];
        delete[] dp;
        return ans;
    }
};

注意代码中

for (const int &it : nums) {
	for (int j = S; j >= it; j--)
		dp[j] += dp[j - it];
}

这部分双层循环实际上就是在填二维表，按行自右向左，因为目标和小于当前元素时，只能不选，因此实际上状态转移方程为 $dp[j]=dp[j]$ ，在这里不用任何操作；而由于状态转移方程为 $dp[j]=dp[j]+dp[j-it]$ ，也就是说对于新的元素，求解可能的目标和方法数只需要比它小的旧的目标和的方法数，因此自右向左求解新的一行，可以避免使用两个一维数组。

自己写了一遍加深印象和理解：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        long sum = 0;
        for(const auto& n:nums) sum += n;
        if((sum+S)% 2!= 0 || S>sum) return 0;
        S = (S+sum)/2;
        vector<int> dp(S+1);
        dp[0] = 1; // 预处理第一行
        //接下来是0-1背包
        for(const auto& n:nums){
            for(int s=S; s>=n; --s)
                dp[s] = dp[s] + dp[s-n];
        }
        return dp[S];
    }
};

总结

题解中的暴力法=DFS=枚举法，而动态规划法是将问题转化为典型的动态规划问题——0-1背包进行求解，填表法，保存计算结果避免重复计算，多是自下而上的动态规划。