494、目标和

leetcode 数组动态规划回溯

Created At : 2020-07-26 00:19

Count:832 Views 👀 :

Comment:

494、目标和
1. 示例 1:
2. 注意:

题解

1、二分递归枚举
2、动态规划

494、目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-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

一共有5种方法让最终目标和为3。

注意:

数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。

提示：

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

链接：https://leetcode-cn.com/problems/target-sum

题解

1、二分递归枚举

public class Solution {
    int count = 0;
    int T;
    public int findTargetsSumWays(int[] nums,int S) {
        T = S;
        calculate(nums,0,0);
        return count;
    }

    private void calculate(int[] nums,int i ,int sum){
        if (i == nums.length) {// 递归结束
            if (sum == T) {
                count++;
            }
        } else {
            // 二分递归
            calculate(nums,i+1,sum-nums[i]);
            calculate(nums,i+1,sum+nums[i]);
        }
    }
}

2、动态规划

状态定义

dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。

状态转移方程

一个方程

$dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]$

改成递推式

$dp[i][j + nums[i]] += dp[i - 1][j]$
$dp[i][j - nums[i]] += dp[i - 1][j]$

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[][] dp = new int[nums.length][2001];
        dp[0][nums[0]+1000] = 1;
        dp[0][-nums[0]+1000] += 1;
        // [i,nums.length]
        for (int i = 1;i < nums.length;i++) {
            // [-1000,1000]
            for (int sum = -1000;sum <= 1000;sum++) {
                // 前一个值大于0
                if (dp[i - 1][sum+1000] > 0) {
                    dp[i][sum+nums[i]+1000] += dp[i - 1][sum+1000];
                    dp[i][sum-nums[i]+1000] += dp[i - 1][sum+1000];
                }
            }
        }
        return S > 1000 ? 0 : dp[nums.length - 1][S+1000];
    }
}

空间优化

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[] dp = new int[2001];
        dp[nums[0]+1000] = 1;
        dp[-nums[0]+1000] += 1;
        // [i,nums.length]
        for (int i = 1;i < nums.length;i++) {
            int[] next = new int[2001];
            // [-1000,1000]
            for (int sum = -1000;sum <= 1000;sum++) {
                // 前一个值大于0
                if (dp[sum + 1000] > 0) {
                    next[sum+nums[i]+1000] += dp[sum + 1000];
                    next[sum-nums[i]+1000] += dp[sum + 1000];
                }
            }
            dp = next;
        }
        return S > 1000 ? 0 : dp][S+1000];
    }
}

转换成背包问题

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int w = sum(nums);
        // 特例过滤
        if (w < S || (w + S) % 2 == 1 || w + S < 0) {
            return 0;
        }
        int W = (w + S) / 2;
        int[] dp = new int[W + 1];
        dp[0] = 1;
        // 目标数为0的取法有一种，就是什么数都不取
        for (int num : nums) {
            for (int i = W; i >= num; i--) {
                // 0,1背包问题。。
                // 之所以条件是 j>=num，因为当j<num时，j-num为负数，负数怎么都取不到，所以这种情况要排除掉
                // 之所以要倒过来遍历，因为当前dp[j]取了num后，dp[j-num]就取不到num了，
                // 所以要倒过来遍历，使得dp[j-num]是没有取num时的所有种取法
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[W];
    }

    public int sum(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res += num;
        }
        return res;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com