LeetCode 494 Target Sum

    
        标签：
        
            动态规划问题
        
    发布于：2022-02-14 21:18:15
    编辑于：2022-02-15 00:22:06
    浏览量：878

概述

https://leetcode.com/problems/target-sum/

可以构造的表达式个数 -> 可以构造的表达式的最大个数

可见其实是一个极值问题，直接上动态规划。

动态规划法（迭代法）

base case：
状态：当前值，处理到第几个运算符
选择：选 + 还是 -？
dp 函数 / 数组的定义：dp[sum][i] = 从第 i 个索引开始，和为 sum 的表达式个数

~~下面是 WA 代码，不想 debug 了~~

offer 要紧，offer 要紧😅

WA 是由于 return 那里忘记加 offset 1000 了。

下面的代码 134 / 139 test cases passed：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size(), vector<int>(2001, 0));
        dp[nums.size()-1][nums.back()+1000] = 1;
        dp[nums.size()-1][-nums.back()+1000] = 1;
        for (int i = nums.size() - 2; i >= 0; i --) {
            for (int s = -1000; s <= 1000; s ++) {
                if (s-nums[i]+1000 >= 0 && s-nums[i]+1000 <= 2000) dp[i][s+1000] += dp[i+1][s-nums[i]+1000];
                if (s+nums[i]+1000 >= 0 && s+nums[i]+1000 <= 2000) dp[i][s+1000] += dp[i+1][s+nums[i]+1000];
            }
        }
        return dp[0][target+1000];
    }
};

原因是 base case 处理不当，如果最后一个值为 0，则应设置为 2，所以应 ++：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size(), vector<int>(2001, 0));
        dp[nums.size()-1][nums.back()+1000] ++;
        dp[nums.size()-1][-nums.back()+1000] ++;
        for (int i = nums.size() - 2; i >= 0; i --) {
            for (int s = -1000; s <= 1000; s ++) {
                if (s-nums[i]+1000 >= 0 && s-nums[i]+1000 <= 2000) {
                    dp[i][s+1000] += dp[i+1][s-nums[i]+1000];
                }
                if (s+nums[i]+1000 >= 0 && s+nums[i]+1000 <= 2000) {
                    dp[i][s+1000] += dp[i+1][s+nums[i]+1000];
                }
            }
        }
        return dp[0][target+1000];
    }
};

动态规划法（递归法）

上面那个解法得遍历所有可能的和，好蠢呀。

下面这个代码 RE 了，数组越界，112 / 139 test cases passed：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size(), vector<int>(2001, -1));
        for (auto& n : dp[nums.size()-1]) n = 0;
        dp[nums.size()-1][nums.back()+1000] ++;
        dp[nums.size()-1][-nums.back()+1000] ++;
        return helper(dp, nums, target, 0);
    }
    
    int helper(vector<vector<int>>& dp, vector<int>& nums, int n, int i) {
        if (dp[i][n+1000] != -1) return dp[i][n+1000];
        dp[i][n+1000] = helper(dp, nums, n + nums[i], i + 1) + helper(dp, nums, n - nums[i], i + 1);
        return dp[i][n+1000];
    }
};

这是因为 n + nums[i] 和 n - nums[i] 可能会越界。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<vector<int>> dp(nums.size(), vector<int>(2001, -1));
        for (auto& n : dp[nums.size()-1]) n = 0;
        dp[nums.size()-1][nums.back()+1000] ++;
        dp[nums.size()-1][-nums.back()+1000] ++;
        return helper(dp, nums, target, 0);
    }
    
    int helper(vector<vector<int>>& dp, vector<int>& nums, int n, int i) {
        if (dp[i][n+1000] != -1) return dp[i][n+1000];
        dp[i][n+1000] = 0;
        if (n + nums[i] >= -1000 && n + nums[i] <= 1000) dp[i][n+1000] += helper(dp, nums, n + nums[i], i + 1);
        if (n - nums[i] >= -1000 && n - nums[i] <= 1000) dp[i][n+1000] += helper(dp, nums, n - nums[i], i + 1);
        return dp[i][n+1000];
    }
};

动态规划法（子集划分问题）

https://labuladong.gitee.io/algo/3/23/76/#三动态规划

我们把数组划分到两个自己，A 中分配加号，B 中分配减号，则：

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)
sum(A) = (target + sum(nums)) / 2

问题转换成了背包问题，取元素刚好填满容量为 (target + sum(nums)) / 2 的背包的取法个数。

这里的 base case 要注意，不能遇到 n == 0 就返回，因为有的项可能为 0，所以其实还有操作的空间。

除此之外，要注意 if ((target + sum) % 2 != 0) return 0;，因为我们是将其转换为背包问题，所以如果没办法整除，n 就有可能是小数，这样就没办法做索引了，如果能换成 float 及哈希表，其实也 okay。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto n : nums) sum += n;
        int n = (target + sum) / 2;
        if ((target + sum) % 2 != 0) return 0;
        vector<vector<int>> dp(nums.size(), vector<int>(1001, -1));
        return helper(dp, nums, n, 0);
    }
    
    int helper(vector<vector<int>>& dp, vector<int>& nums, int n, int i) {
        if (n == 0 && i == nums.size()) return 1;
        if (n < 0 || i >= nums.size()) return 0;
        if (dp[i][n] != -1) return dp[i][n];
        dp[i][n] = helper(dp, nums, n, i + 1) + helper(dp, nums, n - nums[i], i + 1);
        return dp[i][n];
    }
};

回溯法

https://labuladong.gitee.io/algo/3/23/76/#一回溯思路

~~其实这道题也可以回溯法去做，太晚了，我要去睡觉去了。~~

~~拜拜了您勒！~~

算了。

class Solution {
public:
    int count = 0;
    int findTargetSumWays(vector<int>& nums, int target) {
        helper(nums, 0, target, 0);
        return count;
    }
    
    void helper(vector<int>& nums, int target, int sum,  int i) {
        if (i == nums.size()) {
            if (sum == target) count ++;
            return;
        }
        
        helper(nums, target, sum + nums[i], i + 1);
        helper(nums, target, sum - nums[i], i + 1);
    }
};

TLE 了，加个 cache：

。。。

算了，再加和动态规划就没啥大区别了，不玩了，睡觉啦。

Links: leetcode-494-target-sum