目标和

力扣链接

给你一个整数数组 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

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {

    }
};

题意分析

猛一看, 很是烦恼, 不知从何下手
仔细分析, 我们知道: sum 和 target 是两个定值 而且 只有 + - 两种操作 ⇒ target是由两部分组成, 一部分是 -, 一部分是 +. 我们不妨设 - 部分的和是 left, + 部分的和是 right

所以 right - left = target,
由于 left = sum - right ⇒ 2 * right - sum = target
由于 sum 和 target 是定值 ⇒ right = ( target + sum) / 2

题意就转变为: nums数组里有多少组合方式可以使得 + 部分的和 是 (sum + target) / 2(正的一部分确定了, 那么负的那一部分也确定了. 我们此时讨论正的那一部分)

步骤

将问题转化为背包问题 — — 装满容量为 (sum + target) / 2 的背包有多少种方法

1. 向下取整对结果是有影响的, 本质就是 sum + target 的结果是奇数是没有方案的
   比如, sum = 5, target = 2, (sum + target ) / 2 = 3, 找不到一种方案
2. abs(target) > sum, 也是没有方案的
   • target > sum — — 即使全是 + , 也满足不了
   • target < sum — — 即使全是 -, 也满足不了

进一步转化为 01背包问题 — — 因为每一件物品 只能用一次

dp的含义

dp[j] — — 装满容量为j的背包有多少种方法

递推公式

dp[j]的来源有哪一些呢 ?
其实, 我们知道 nums[i], 就可以推出dp[j]
比如, j = 5:
已经有一个 1 (nums[i]), 那么就有dp[4] 种装满容量为5的背包
已经有一个 2 (nums[i]), 那么就有dp[3] 种装满容量为5的背包
已经有一个 3 (nums[i]), 那么就有dp[2] 种装满容量为5的背包
已经有一个 4 (nums[i]), 那么就有dp[1] 种装满容量为5的背包
已经有一个 5 (nums[i]), 那么就有dp[0] 种装满容量为5的背包

那么dp[5] = dp[0] + dp[1] + dp[2] + dp[3] + dp[4] ⇒ dp[j] += dp[ j - nums[i] ]

dp数组初始化

dp[0] = dp[0]
dp[1] = dp[0]
dp[2] = dp[0] + dp[1]

… … … …

dp[n] = dp[0] + dp[1] + … … + dp[n - 1]

我们发现 dp[0] 是一切递推的起源, 此时我们必须初始化 dp[0] = 1

遍历顺序

从 dp[0] 到 dp[n] , 故可以得出是从小到大的遍历顺序

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        // 本题转化为 -- -- 有多少种方式组合成 "最终正数和是positive(或者负数和是sum - positive)"
        int dp[1005] = {0};
        dp[0] = 1;
        
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if(abs(target) > sum)  return 0;
        int Sum = target + sum;
        if(Sum % 2 != 0)  return 0;
        int positive = Sum / 2;
        
        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = positive; j >= nums[i]; j--)
            {
                dp[j] += dp[j - nums[i]];  // 求组合数的递推公式
            }
        }
        
        return dp[positive];
    }
};