Leetcode 494. 目标和 dp

地址 https://leetcode-cn.com/problems/target-sum/

给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。


示例 1：
输入：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

示例 2：
输入：nums = [1], target = 1
输出：1
 

提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

解答
1 暴力遍历 每个元素可以有正负两个选择 O(2^20)
2 dp 由于有负数不可作为索引。 将所有计算额外加上了1000。
3 dp 通过公式推导，变成了01背包。

方案1
dfs 暴力遍历每个元素前面添加+或者-
到最后查看得到的计算结果是否等于target
复杂度比较高. 每个元素有+-两个选择，一共20个元素，那么暴力遍历完成就是O(2^(nums.length))

class Solution {
public:
    int ans = 0;
    void dfs(vector& nums,int idx,int sum,int target){
        if(idx == nums.size()){
            if(sum == target) ans++;
            return;
        }

        sum +=nums[idx];
        dfs(nums,idx+1,sum,target);
        sum -= 2*nums[idx];
        dfs(nums,idx+1,sum,target);
        return;
    }

    int findTargetSumWays(vector& nums, int target) {
        dfs(nums,0,0,target);

        return ans;
    }
};

方案2
dp[x][y] 表示在数组前x个元素中，计算得出结果为y的方案数。
那么dp[x][y] = dp[x-1][y-val] + dp[x-1][y+val];
其中val是nums中第x个数的值。
1 该值前选择减号，那么前x-1个元素可以计算出y+val的方案数 再减去val就可以得到前x个元素计算得出y的方案数。
同样的
2 该值前选择加号，那么前x-1个元素可以计算出y-val的方案数 再加上val就可以得到前x个元素计算得出y的方案数。
1+2 就是dp[x][y].

class Solution {
public:
	int findTargetSumWays(vector& nums, int target) {
		int dp[22][2010]; memset(dp, 0, sizeof dp);
		dp[0][1000] = 1; target += 1000;
		for (int i = 1; i <= nums.size(); i++) {
			int val = nums[i - 1] ;
			for (int j = 2000; j >= 0; j--) {
				if (j - val >= 0) {
					dp[i][j] += dp[i - 1][j - val];
				}
				if (j + val <= 2000) {
					dp[i][j] += dp[i - 1][j + val];
				}
			}
		}

		return dp[nums.size()][target];
	}
};

我的视频题解空间