494. 目标总和

给你一个整数数组 nums 和一个整数目标。

您想要通过在 nums 中的每个整数之前添加符号“+”和“-”之一来构建 nums 的表达式，然后连接所有整数。

例如，如果 nums = [2, 1]，您可以在 2 之前添加一个“+”，在 1 之前添加一个“-”，并将它们连接起来构建表达式“+2-1”。
返回您可以构建的不同表达式的数量，其计算结果为目标。

示例1：

输入：nums = [1,1,1,1,1]，目标 = 3
输出：5
说明：有 5 种分配符号的方法，使 nums 的总和为目标 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]，目标 = 1
输出：1

限制：

1
0
0
-1000
原始页面

尽管回溯在这里很有用，我们可以使用动态规划来解决这个问题，以实现更低的时间复杂度。

public int findTargetSumWays(int[] nums, int target) {
    /**
    sum(neg) + sum(pos) = sum(nums);
    sum(pos) - sum(neg) = target;
    sum(pos) = (sum(nums) + target) / 2 
     */
    int sum = Arrays.stream(nums).sum();
    // that means the sum of the positive number is invalid, because the nums do not conclude float
    if((sum+target)%2 != 0|| Math.abs(target) > sum){
        return 0;
    }

    // here we find the summary of the positive numbers
    int pos = (sum + target) >>1;

    // dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods   
    int[][] dp = new int[nums.length+1][pos+1];

    // if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
    dp[0][0] = 1;

    // if(nums[0]  j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            }
        }
    }
    // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
    return dp[nums.length][pos];       

}

登录后复制

笔记

1、初始化dp数组很重要尤其是这里重要的是要弄清楚0的含义

    以上就是LeetCode DayDynamic Programming Part 4的详细内容，更多请关注php中文网其它相关文章！