LeetCode 494 Target Sum

动态规划问题 2022-02-14 21:18:15 2022-02-15 00:22:06 222 次浏览

概述

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

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

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

动态规划法(迭代法)

  1. base case:
  2. 状态:当前值,处理到第几个运算符
  3. 选择:选 + 还是 -?
  4. 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:

。。。

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/