目标和力扣--494

目录

题目

思路

1. 确定dp数组以及下标的含义

2. 确定递推公式

3.初始化dp数组

4.确定遍历顺序

代码

题目

给你一个非负整数数组 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

思路

对于target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就转化为，用nums装满容量为j的背包，有几种方法。

这里的left，就是bagSize，也就是我们后面要求的背包容量。

如果（target+sum）/2不是整数呢？那就说明找不到，没有方案，直接返回0即可

1. 确定dp数组以及下标的含义

dp[j]表示填满容量为j的背包可以有几种方法

2. 确定递推公式

假设j=5

如果里面有1个物品  那么有dp【4】种方法可以凑出来dp【5】

如果里面有2个物品  那么有dp【3】种方法可以凑出来dp【5】

如果里面有3个物品  那么有dp【2】种方法可以凑出来dp【5】

如果里面有4个物品  那么有dp【1】种方法可以凑出来dp【5】

如果里面有5个物品  那么有dp【0】种方法可以凑出来dp【5】

dp【j】+=dp【j-nums【i】】

3.初始化dp数组

对于dp【0】应该初始化为多少呢？

假如数组是dp【0】，target=0

sum也等于0，所以left只能等于0 ，只有一种情况

dp[0]=1

4.确定遍历顺序

外层物品内层背包

遍历物品放在外循环，遍历背包在内循环，且内循环倒序（为了保证物品只使用一次）。

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if (Math.abs(target) > sum) return 0;
        if((target+sum)%2!=0){
            return 0;
        }
        int a=(target+sum)/2;
        int[] dp=new int[a+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=a;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[a];
    }
}