🚩[LeetCode]Dp494 目标和 [ 01背包 ]

🚩传送门：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

解题思路：回溯

数组 的每个元素都可以选择添加符号 或 ，因此每个元素有 种添加符号的方法， 个数共有 种添加符号的方法，对应 种不同的表达式。当 个元素都添加符号之后，即得到一种表达式，如果表达式的结果等于目标数 ，则该表达式即为符合要求的表达式。

可以使用回溯的方法遍历所有的表达式，回溯过程中维护一个计数器 ，当遇到一种表达式的结果等于目标数 时，将 的值加 。遍历完所有的表达式之后，即可得到结果等于目标数 的表达式的数目。

复杂度分析

时间复杂度：，其中 为数组 的长度 。

回溯需要遍历所有不同的表达式，共有 种不同的表达式，每种表达式计算结果需要 的时间，因此
总时间复杂度是 。

空间复杂度：，其中 为数组 的长度。空间复杂度取决于递归使用的栈空间，栈的深度不
超过 。

代码

🚩官方代码

class Solution {
    int count = 0;
    //计算总和
    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }
    public void backtrack(int[] nums, int target, int index, int sum) {
        //到达规定末尾深度,判断此式是否合法
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            //递归负数
            backtrack(nums, target, index + 1, sum + nums[index]);
            //递归正数
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

解题思路：动态规划

记数组的元素和为 ，添加 号的元素在数组中之和为 ，则其余添加 的元素在数组中之和为 ，得到的表达式的结果为

即

由于数组 中的元素都是 非负整数 ，显然 也必须是 非负整数 ，得上式成立前提 是 非负偶数 。若不符合该条件可直接返回 。

解释： nums 元素都是非负整数，原因是 nums 全是 正数 或 0 。 为什么 neg 也必须是非负整数 ？ 由于 nums 数组的元素特性决定了 sum≥0 ，且 -sum≤target≤sum ，因此 sum-target≥0 ，非负性 证毕 整数性证明？🦄我尼玛直接陀螺旋转裂开哦

若上式成立，问题转化成在数组 中选取若干元素，使得这些元素之和等于 ，计算选取元素方案数。

👉 定义 表示在数组 的前 个数中选取元素，使得这些元素之和等于 的方案数。

假设数组 的长度为 ，则最终答案为 。

当没有任何元素可以选取时，元素和只能是 ，对应的方案数是 ，因此动态规划的边界条件是：

计算 的值 [ 01背包模型 ]
当 时，对于数组 中的第 个元素 （ 的计数从 开始），遍历 ，

• 若 时，则不能选 ，此时有 ；

• 若 时，则考虑 选 或 不选 的问题 [ 其实不用考虑，能选一定选 ]

  总方案数 不选的方案数 选择的方案数

  • 若选则 ，方案数是
  • 若不选 ，方案数是

因此状态转移方程如下：

最终得到 的值即为答案。由此可以得到空间复杂度为 的实现。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        //1. 求数组元素和
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        //2. 检查sum - target是否是非偶数
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                //3. 默认不选nums[i]
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    //4. 大于就选
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

由于 的每一行的计算只和上一行有关，因此可以使用滚动数组的方式，去掉 的第一个维度，将空间复杂度优化到 。

实现时，内层循环需采用倒序遍历的方式，这种方式保证转移来的是 中的元素值。

复杂度分析

时间复杂度：，其中 为数组 的长度， 是数组 的
元素和， 是目标数。动态规划有 个状态，需要计算每个状态的值。

空间复杂度：，其中 是数组 的元素和， 是目标数。使用空
间优化的实现，需要创建长度为 的数组 。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        //1. 求和
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        //2. 条件预判
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            //3. 一维数组倒序
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
}