LeetCode494 目标和

发表于 | 分类于 |
字数统计: 499 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/target-sum/

题意

给你一个整数数组 nums 和一个整数target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，要求和等于target

解法

首先最直观的解法考虑dfs，时间复杂度较高，但实现起来比较容易
用dp来进行优化，令dp[i][j]表示前i个数运算结果为j的方案数
由于运算结果可能为负数，所以可以令dp[i][j]表示前i个数运算结果为j - 1000的方案数
进行递推求解，最后dp[n][1000]即为最后的答案，由于每次状态转移只会用到上一次的状态
所以考虑滚动数组进行优化

更优的解法是将问题转化为一个01背包问题，设数组元素和为$sum$，取符号的数字和为$neg$
可以计算得到$neg = (sum - target) / 2$
然后就可以将问题转化成一个和为neg的方案数的背包问题

代码

直接dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int ans;
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> dp(2, vector<int>(3010));
        // dp[i][j]表示前i个数计算结果为j的个数
        dp[0][1000] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 2000; j++) {
                dp[(i + 1) % 2][j] = dp[i % 2][j + nums[i]];
                if (j >= nums[i]) dp[(i + 1) % 2][j] += dp[i % 2][j - nums[i]];
                // if (j == 1001) cout << i + 1 << ' ' << j << ' ' << dp[i + 1][j] << endl;
            }
        }
        return dp[n % 2][1000 + target];
    }
};

01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int ans;
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), sum = accumulate(nums.begin(), nums.end(), 0);
        int neg = sum - target;
        if (neg < 0 || neg % 2 == 1) return 0;
        neg /= 2;
        vector<int> dp(neg + 1);
        dp[0] = 1;
        // dp[i]表示和为i的个数
        for (int i = 0; i < n; i++) {
            for (int j = neg; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[neg];
    }
};