力扣 剑指 Offer II 102. 加减的目标值

题目来源：https://leetcode.cn/problems/YaVDxD/

大致题意：
给一个正整数数组和目标值 target，可以加上或减去每个数组元素，求有多少种方式可以得到目标值

思路

设原数组元素和为 sum，减去的数组元素和为 neg，那么剩余的数组元素和为 sum - neg，于是有(sum - neg) - neg = target

所以sum - target = 2 * neg

因此可以求出 neg 的值，那么该题就变成了求数组的子序列和为 neg 的个数

使用 dp[i][j] 表示数组前 i 个元素可以组成和为 j 的个数，于是有

dp[i][j] = dp[i - 1][j], j < nums[i]
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]], j >= nums[i]

可以看出，dp[i] 的值只与 dp[i - 1] 有关，且 dp[i][j] 只与 dp[i - 1][k]（其中 k 小于 j）有关，于是可以节约空间直接使用滚动数组

初始时，dp[0] = 0，0 个数组成 0 的选择有 1 种

代码：

public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int diff = sum - target;
        // 因为数组都为正整数，所以 diff 小于 0 时，不会有子序列为 diff / 2
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int t = diff / 2;
        // 滚动数组
        int[] dp = new int[t + 1];
        // 初始化
        dp[0] = 1;
        // 遍历数组
        for (int num : nums) {
            // 从后往前遍历可以避免重写的低位元素对高位元素造成影响
            for (int j = t; j >= num; j--) {
                // 等价于 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]
                dp[j] += dp[j - num];
            }
        }
        return dp[t];
    }