leetcode-494-目标和

目标和

题面

leetcode题目

给你一个整数数组 \(nums\) 和一个整数 \(target\) 。

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

• 例如，\(nums = [2, 1]\) ，可以在 \(2\) 之前添加 \(+\) ，在 \(1\) 之前添加 \(-\) ，然后串联起来得到表达式 \(+2-1\) 。

返回可以通过上述方法构造的、运算结果等于 \(target\) 的不同 表达式 的数目。

example

输入：\(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 \leq nums.length \leq 20\)
• \(0 \leq nums[i] \leq 1000\)
• \(0 \leq sum(nums[i]) \leq 1000\)
• \(-1000 \leq target \leq 100\)

题解

总体思路

还是考虑01背包，因为只有两种状态，当前值前添加\(+\)和添加\(-\)。
考虑\(dp[i][j]\)表示在维护结束第\(i\)个元素后目标和为\(j\)时的表达式的数量，那么有:

• 当前值前添加\(+\)时，\(dp[i][j] = dp[i-1][j - nums[i]]\)
• 当前值前添加\(-\)时，\(dp[i][j] = dp[i-1][j + nums[i]]\)

于是有: \[ dp[i][j] = \left\{ \begin{array}{rcl} dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]] & & {i > 0}\\ 1 & & {i = 0\land j=0} \end{array} \right. \] 考虑到我们c++中维护负数下标的复杂性，我们不妨直接把数字0定义成一个比较大的值，然后向左右扩展。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _DEBUG
class Solution
{
public:
    const int MAX = 2011; // 1010 = 0
    const int ZERO = 1010;
    int findTargetSumWays(vector<int> &nums, int target)
    {
        int len = nums.size();
        int dp[len + 1][MAX];
        memset(dp, 0, sizeof(dp));
        dp[0][ZERO] = 1;

        for (int i = 1; i <= len; i++)
        {
            int num = nums[i - 1];
            // 选择+或者选择-
            for (int k = 1; k < MAX; k++)
            {
                if (k - num >= 0)
                {
                    dp[i][k] += dp[i - 1][k - num];
                }
                if (k + num < MAX)
                {
                    dp[i][k] += dp[i - 1][k + num];
                }
#ifdef _DEBUG
                if (dp[i][k] > 0)
                {
                    cout << "i: " << i << " k: " << k << " dp: " << dp[i][k] << endl;
                }
#endif
            }
        }
        return dp[len][ZERO + target];
    }
};

// for test
int main()
{
    Solution s;
    vector<int> t1{1, 1, 1, 1, 1};
    cout << s.findTargetSumWays(t1, 3) << endl;
    vector<int> t2{1};
    cout << s.findTargetSumWays(t2, 1) << endl;
    return 0;
}