【LeetCode】494.目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+‘ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+‘ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

算法1（暴力递归）

时间复杂度：\(O(2^n)\)，指数级，爆炸
选择符号时进行移项，符号取反，判断是否达到target等价于target-左式是否等于0。递归的本质即为二叉树的遍历。

class Solution {
public:
    int res = 0;

    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums, target, 0);
        return res;    
    }

    void backtrack(vector<int>& nums, int rest, int i) {
        //触发结束条件
        if (nums.size() == i) {
            if (rest == 0) res ++;
            return;
        }
        
        //给nums[i]选择"-"号
        rest += nums[i];
        backtrack(nums, rest, i + 1);
        //撤销选择
        rest -= nums[i];

        //给nums[i]选择"+"号
        rest -= nums[i];
        backtrack(nums, rest, i + 1);
        //撤销选择
        rest += nums[i];
    }
};

算法2（带有备忘录的递归）

时间复杂度：\(O(n^k)\)
算法1的暴力递归过程中，有许多的重复子问题，例如当nums[i]==0时，会执行两次backtrack(nums, rest, i + 1)，为了消除这一类的重叠子问题，我们可以考虑利用备忘录的技巧消除。在每计算一组rest和i对应的结果时存到备忘录中（转换为字符串形式作为哈希表的键）。
dp函数定义：dp(nums,rest,i)表示选择至第i个数字且当前的计算结果为rest时（此处为rest为target与已选择的计算结果的差值），是否能够成功达成目标。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        return dp(nums, target, 0);
    }

    //备忘录
    unordered_map<string, int> memo;
    int dp(vector<int>& nums, int rest, int i) {
        //base case
        if (i == nums.size()) {
            if (rest == 0) return 1;
            else return 0;
        }

        string key = to_string(rest) + "+" + to_string(i);
        if (memo.count(key)) return memo[key];

        int result = dp(nums, rest - nums[i], i + 1) + dp(nums, rest + nums[i], i + 1);
        memo.insert(make_pair(key, result));
        
        return result;
    }
};

算法3（动态规划）

时间复杂度：\(O(n^2)\)

我们用sum(A)和sum(B)分别表示选择的+号和-号的数量，则易知以下关系：

原问题则转化为：nums中存在几个+号，使得A中的元素和为\(\frac{target+sum(nums)}{2}\)。

至此即转换为了背包问题，即给你一个容量为sum的背包，n个物品，第i个物品的重量是nums[n-1]，问有多少种方法可以将背包恰好装满。

dp数组定义：dp[i][j]表示，若只在前i个物品中选择，背包容量为j，能够恰好装满的方法总数。
由该定义推知dp[0][j]=0，即没有物品可供选择，方法数为0。dp[i][0]=1，即背包容量为0，只有采取什么都不装的方法，即方法数为1。

状态转移分析：dp[i][j]可以分为两种情况：

1. 选择了第i件物品，则dp[i][j]=dp[i-1][j - nums[i-1]]
2. 没有选择第i件物品，则dp[i][j]=dp[i-1][j]

状态转移方程即为：

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto num : nums) sum += num;
        //以下两种情况找不到合适的表达式
        if (sum < target || (target + sum) % 2 == 1)
            return 0;
        return subsets(nums, (sum + target) / 2);
    }

    //计算nums中有几个子集和为sum
    int subsets(vector<int>& nums, int sum) {
        int n = nums.size();
        int dp[n + 1][sum + 1];
        memset(dp, 0, sizeof(dp));

        //base case
        for (int i = 0; i <= n; i ++ ) dp[i][0] = 1;

        for (int i = 1; i <= n; i ++ ) {
            for (int j = 0; j <= sum; j ++ ) {
                //如果背包容量大于等于当前物品重量
                if (j >= nums[i - 1])
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                //背包容量小于物品重量
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][sum];
    }
};

【LeetCode】494.目标和

原文：https://www.cnblogs.com/I-am-Sino/p/15152537.html