2. ＜ tag dynamic programming and 0-1 knapsack problem ＞ lt.416 Split equal sum subset + lt.1049 Weight of the last stone II

lt.416. To divide into equal and subsets

[ Case needs ]

[ Train of thought analysis 1 , Dynamic programming ]

[ Code implementation ]

class Solution {
    
    public boolean canPartition(int[] nums) {
    
       
        //  The volume of the backpack is Sum/2;
        //  The goods to be put in the backpack ( The elements in the collection ) Weight is   The value of the element ,  The value is also the value of the element ;
        //  The backpack is just full ,  Indicates that the sum of  Sum / 2 Subset ;
        //  Every element in the backpack cannot be put in repeatedly 

        //1.  determine DP The meaning of arrays and subscripts 
        //0-1 knapsack problem , dp[i][j], 0~i-1 The numbered items are put into a container with a capacity of j The maximum value you get from your backpack 
        //  This topic : dp[j]  Indicates that the backpack capacity is j,  The maximum can be made up j The sum of the subsets of is dp[j]
        int sum = 0;
        int n = nums.length;

       int target = 0;

        for(int x : nums){
    sum += x;}
        if(sum % 2 != 0)return false;
        
        target = sum / 2;
        
        int[] dp = new int[sum / 2 + 1];
        //2.  Determine the recurrence formula 
        //0,1 knapsack : dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        //dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        for(int i = 0; i < n; i++){
    
            for(int j = target; j >= nums[i]; j--){
    
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;

    }
}

lt.1049. The weight of the last stone II

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]