1、思路

• 设所有添加+的数字之和为p，所有添加-的数字之和为q，按照题目要求有p - q = target，设数组中所有数字之和为sum，即p + q = sum，则有p = (target + sum) / 2；

• 问题可以转化为在数组中找出和p为(target + sum) / 2的数字，给它们都添加+，然后给其余数字添加-，那么最终的计算结果就是target；

• 状态转移方程dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，其中dp[i][j]表示在前i个数字中选出若干数字使和等于j的方法的数目，两种情况分别表示选择当前第i件物品和不选当前第i件物品；

• 计算dp[i][j]时，只需要用到上一行的dp[i - 1][j]和dp[i - 1][j - nums[i]]，若从右往左计算，可以将空间压缩成一维数组，状态转移方程为dp[j] += dp[j - num];；

• dp初始化：
  1、j == 0，一个数字都不选，和为0的方法有一种；
  2、i == 0 && j > 0，一个数字都不选，和大于0的方法有0种；

• 时间复杂度为 $O(N * target)$，空间复杂度为 $O(target)$。

2、代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int &num : nums) sum += num;

        //若 target + sum 为奇数，就不可能找到和为 (target + sum) / 2 的数字
        if (abs(target) > sum || (sum + target) % 2 == 1) return 0;

        vector<int> dp((target + sum) / 2 + 1, 0);
        dp[0] = 1;

        for (int &num : nums)
        {
            for (int j = dp.size() - 1; j >= num; -- j)
            {
                dp[j] += dp[j - num];
            }
        }

        return dp.back();
    }
};