代码随想录笔记_动态规划_494目标和

代码随想录二刷笔记记录

LC494.目标和

---

题目

01背包

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

提示：

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

---

思路分析

思路：
思路：取两边(或称分堆)，左边为加法之和，右边为减法之和

例： [1,1,1,1,1]

假设左边由 [1,1,1,1] 组成，加法堆总和为 4，则减法堆总和为 sum - 4 = 1。即右边由 [1] 组成

设 x = 4 则 target = x - (sum - x)，可得 x = (sum + target) / 2

动态规划五部曲

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

dp[j] : 装满容量 j 的背包，由 dp[j] 种方法

2.确定递推公式

如何推导 dp[j] ?

不考虑 num[i] 的情况，有 dp[j] 种方法

考虑 num[i] 的情况，凑成 dp[j] 就有 dp[j - num[i]] 种方法。

例如： dp[j], j = 5
如：dp[j], j =5
已知一个1(nums[i]),就有dp[4]种方法,合成 dp[5]
已知一个2(nums[i]),就有dp[3]种方法,合成 dp[5]
已知一个3(nums[i]),就有dp[2]种方法,合成 dp[5]
已知一个4(nums[i]),就有dp[1]种方法,合成 dp[5]
已知一个5(nums[i]),就有dp[0]种方法,合成 dp[5]
累加上述所有的方法，就是合成dp[5]的所有方法
解答所有组合类问题，都考虑采用这个公式:

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

3.初始化

由递推公式 dp[j] += dp[j - nums[i]] 可知，dp[0] 要被初始化为1,如果dp[0] 初始化为0，则递归结果都会是0

dp[0] = 1: 代表装满容量为0的背包，有1种方法，装0件物品
dp[j] 的其他下标都由dp[0]累加而来，因此其他下标都初始化为0

4.遍历顺序

for(int i = 0; i < nums.length;i++){ //遍历物品
	for(int j = bagSize; j >= nums[i]; j--){//遍历背包容量
		//每个元素取一次，无论加减，因此逆序遍历
		dp[j] += dp[j - nums[i]];
	}
}
1
2
3
4
5
6

5.推演分析

例：nums: [1, 1, 1, 1, 1], target: 3
bagSize = (target + sum) / 2 = (3+5) / 2 = 4

这里 bagSIze 可以理解为左边的数值 [1,1,1,1] 减去右边的数值 [1] 则会得到 target

bagSize 就是子集数组的大小

特判1：(sum + target) / 2 是向下取整，因此，以 sum = 5， target = 2 为例，则无解

if((target + sum) % 2 == 1) return 0;
1

特判2

因为 [1,1,1,1,1] 的和为 5，即 sum = 5。因此，若 target 的绝对值大于 5，即超过了数组的上限，也无解。

if(abs(target) > sum) return 0;
1

---

代码实现

完整代码实现

public int findTargetSumWays(int[] nums, int target) {
        if (null == nums || nums.length == 0) return 0;
        int sum = Arrays.stream(nums).sum();
        //特判1:无解
        if ((target + sum) % 2 == 1) return 0;
        //特判2:target的绝对值大于 sum,无解
        if (Math.abs(target) > sum) return 0;
        //背包容量(子集数组大小)
        int bagSize = (target + sum) / 2;
        //初始化
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        //遍历
        for (int i = 0; i < nums.length; i++) { //遍历物品
            for (int j = bagSize; j >= nums[i]; j--) { //遍历背包
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

小结

LC416和LC1049考察容量 j 的背包，最多能装多少物品

本题考察的是：装满容量 j 的背包，有几种方法。

这类组合问题常用递推公式：

dp[j] += dp[j - num[i]]
1