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\le nums.length\le 20$
• $0\le nums[i]\le 1000$
• $0\le sum(nums[i])\le 1000$
• $-1000\le target\le 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]=\{\begin{array}{rcl}dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]& & i>0\\ 1& & i=0\wedge j=0\end{array}$$ 考虑到我们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;
}