Code Casual Recording Notes_Dynamic Programming_416 Segmentation and Subsetting

代码随想录二刷笔记记录

LC416.分割等和子集

---

题目

01背包

给你一个 只包含正整数 的 非空 数组 nums .请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等.

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] .

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集.

---

思路分析

思路：
Divide the array into two subsets,make subset A 和子集 B the sum is equal

-> Find the set appears sum/2 的Subset sum.can be divided into two equal subsets

加入01背包的概念

1.背包的容量 sum/2
2.The weight of the item that needs to be put in the backpack is the value of the elementnums[i],价值也是nums[i]
3.背包如果正好装满,Indicates that equal subsets were found
4.Every element in the backpack is non-repeatable

动态规划五部曲

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

dp[j]:Represents the sum of one of the subsets that makes the two subsets equal.
简单地说就是(符合题意)Subset sum

2.确定递推公式

dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])
The weight and value of the items in this question are both nums[i]

3.初始化

Known from knowledge of rolling arrays,numThe elements in are all positive integers,则dp初始化为0即可.

Only all are initialized to0,The maximum value can only be taken during derivation.

反之,如果 num The elements in have negative numbers,则dp中的非0Subscript elements need to be initialized to negative infinity.

4.遍历顺序

for(int i = 0;i < nums.length;i++){
    //先遍历物品,That is, the array value
	for(int j = target; j >= nums[i];j --){
    //遍历背包容量
		//注意,Each element can only be placed once,Hence the reverse order,Avoid replay
		dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
	}
}

5.推演分析

以 [1,5,5,11] 为例

容量 j	0	1	2	3	4	5	6	7	8	9	10	11
元素1	0	1	1	1	1	1	1	1	1	1	1	1
元素5	0	1	1	1	1	5	6	6	6	6	6	6
元素5	0	1	1	1	1	5	6	6	6	6	6	11

图示:

---

代码实现

完整代码实现

public boolean canPartition(int[] nums) {
    
        if (null == nums || nums.length == 0) return false;
        // num 求和
        int sum = Arrays.stream(nums).sum();
        // 如果 sum 为奇数,Indicates that no two identical subsets could be found
        if (sum % 2 == 1) return false;
        // 背包容量
        int bagSize = sum /2;
        // 初始化dp数组
        int[] dp = new int[bagSize + 1];
        for (int i = 0; i < nums.length; i++) {
     // 遍历元素
            for (int j = bagSize; j >= nums[i]; j--) {
     // 遍历背包
                dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
            }
        }
        return bagSize == dp[bagSize];
    }

---