Dynamic programming - 416. Segmentation and subsets

1 Title Description

To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

2 Title Example

Example 1：
Input ：nums = [1,5,11,5]
Output ：true
explain ： Arrays can be divided into [1, 5, 5] and [11] .

Example 2：
Input ：nums = [1,2,3,5]
Output ：false
explain ： An array cannot be divided into two elements and equal subsets .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/partition-equal-subset-sum

3 Topic tips

1 <= nums.length <= 200
1 <= nums[i] <= 100

4 Ideas

Ontology ideas source code Capriccio
link ：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html#_01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
knapsack problem , Everybody knows , Yes N Items and one can carry a maximum weight of W The backpack . The first i The weight of the item is weight[i], The value is value[i] . Each item can only be used once , Solve which items are loaded into the backpack, and the total value of the items is the largest .

There are many ways to solve the knapsack problem , Common are ：01 knapsack 、 Completely backpack 、 Multiple backpack 、 Group backpack and hybrid backpack, etc .

Pay attention to whether the goods in the title description can be repeatedly put into .

That is, if a commodity can be put in repeatedly, it is a complete backpack , And can only be put in once is 01 knapsack , The writing method is still different .

To be clear, what we want to use in this question is 01 knapsack , Because we can only use elements once .

Return theme ： First , This question asks whether there is a total of sum / 2 Subset .

So let's answer this question one by one , Look at the knapsack problem. If you solve it .

Only the following four points have been identified , To put 01 The knapsack problem comes to this problem .

The volume of the backpack is sum / 2
The goods to be put in the backpack （ The elements in the set ） Weight is The value of the element , The value is also the value of the element
If the backpack is just full , Indicates that the sum of sum / 2 Subset .
Every element in the backpack can't be put repeatedly .

After the above analysis , We can apply 01 knapsack , To solve this problem .
The five parts of dynamic planning are analyzed as follows ：

1. determine dp The meaning of arrays and subscripts
   01 In the backpack ,dp[j] Express ： Capacity of j The backpack , The value of the items carried can be up to dp[j].
   Get to the point ,dp[j] Express The total capacity of the backpack is j, The maximum can be made up j The sum of the subsets of is dp[j].
2. Determine the recurrence formula
   01 The recurrence formula of knapsack is ：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
   This topic , It's equivalent to putting values in your backpack , So the object i The weight of is nums[i], Its value is also nums[i].
   So the recurrence formula ：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3. dp How to initialize an array
   stay 01 knapsack , A one-dimensional dp How to initialize , Already said ,
   from dp[j] By definition , First dp[0] It must be 0.
   If the value given by the topic is a positive integer, then it is not 0 Subscripts are initialized to 0 That's all right. , If the title gives a negative value , So no 0 The subscript is initialized to negative infinity .
   In this way, we can make dp The maximum value of array in the process of recursive formula , Instead of being overwritten by the initial value .
   In this topic A non empty array containing only positive integers , So not 0 The subscript element is initialized to 0 That's all right. .
4. Determine the traversal order
   In dynamic programming ： About 01 knapsack problem , You should know this ！（ Scrolling array ） (opens new window) It has been stated in ： If you use one dimension dp Array , Item traversal for Loop on the outer layer , Traversing the backpack for Loop on the inner layer , And inner layer for Loop backward traversal ！
5. Give an example to deduce dp Array
   dp[j] The value of must be less than or equal to j Of .
   If dp[j] == j explain , The sum of subsets in the set can be summed up j, It's important to understand this .

5 My answer

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
    
            sum += num;
        }
        // The sum is odd , It can't be divided equally 
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++){
    
            for(int j = target; j >= nums[i]; j--){
    
                // goods  i  The weight of is  nums[i], Its value is also  nums[i]
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}