Leetcode brush question: dynamic planning 09 (weight of the last stone II)

1049. The weight of the last stone II

Force button topic link

questions ： secondary

There is a pile of stones , The weight of each stone is a positive integer .

Every round , Choose any two stones , Then smash them together . Suppose the weights of the stones are x and y, And x <= y. The possible results of crushing are as follows ：

If x == y, Then both stones will be completely crushed ;
If x != y, So the weight is x The stone will be completely crushed , And the weight is y The new weight of the stone is y-x.
Last , There's only one stone left . Return the minimum possible weight of this stone . If there is no stone left , Just go back to 0.

Example ：
Input ：[2,7,4,1,8,1]
Output ：1
explain ：
Combine 2 and 4, obtain 2, So the array turns into [2,7,1,8,1],
Combine 7 and 8, obtain 1, So the array turns into [2,1,1,1],
Combine 2 and 1, obtain 1, So the array turns into [1,1,1],
Combine 1 and 1, obtain 0, So the array turns into [1], This is the optimal value .

Tips ：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

dp[j] by Capacity of j The backpack
If you take a stone every time stones[i] be dp[j] The remaining capacity of is Math.max(dp[j],dp[j-stones[i]]+stone[i]),
If you don't take this stone , Is the same
/**
* Divide the total weight of the stones into two piles , Subtract the last , Then we can get whether there are any remaining stones in the end
* namely ： Find the stone that can be loaded when the capacity is half , Compare with the remaining stone capacity , You can get the required remaining stone weight
* 1. dp[j]: Capacity of j The maximum number of stones a backpack can hold .j Take half of the total number of stones ,dp[j]<=j
* Because it needs to be subtracted from the weight of the remaining stones
* 2. Determine the recurrence formula stones It is the number of stones that the backpack has loaded ,dp[j-stones[i]] Ask for stones that can be filled in the remaining capacity of the backpack
* 3.dp Array initialization ：dp[j] Take the maximum value every time , So take 0 Can ,dp[j] The initial value will not be overwritten , The weight of the stone must be >0
* 4. Determine the traversal order ： First traverse the number of stones , Go through the backpack again （ In the past, it will lead to what has been obtained dp[i] Be reused ）
*/

package com.programmercarl.dynamic;

/** * @ClassName LastStoneWeightII * @Descriotion TODO * @Author nitaotao * @Date 2022/7/27 15:55 * @Version 1.0 * https://leetcode.cn/problems/last-stone-weight-ii/ * 1049.  The weight of the last stone  II **/
public class LastStoneWeightII {
    
    public int lastStoneWeightII(int[] stones) {
    
        /** *  Divide the total weight of the stones into two piles , Subtract the last , Then we can get whether there are any remaining stones in the end  *  namely ： Find the stone that can be loaded when the capacity is half , Compare with the remaining stone capacity , You can get the required remaining stone weight  * 1. dp[j]: Capacity of j The maximum number of stones a backpack can hold .j Take half of the total number of stones ,dp[j]<=j *  Because it needs to be subtracted from the weight of the remaining stones  * 2.  Determine the recurrence formula  stones It is the number of stones that the backpack has loaded ,dp[j-stones[i]] Ask for stones that can be filled in the remaining capacity of the backpack  * 3.dp Array initialization ：dp[j] Take the maximum value every time , So take 0 Can ,dp[j] The initial value will not be overwritten , The weight of the stone must be >0 * 4. Determine the traversal order ： First traverse the number of stones , Go through the backpack again （ In the past, it will lead to what has been obtained dp[i] Be reused ） */
        // Total stone weight and 
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
    
            sum += stones[i];
        }
        // /  Rounding down  sum/2>=target
        int target = sum / 2;
        //dp[j]: Capacity of j The maximum number of stones a backpack can hold .j Take half of the total number of stones ,dp[j]<=j
        // j  Capacity  dp[j]  Capacity of j The backpack 
        int[] dp = new int[target + 1];
        // First traverse the stone 
        for (int i = 0; i < stones.length; i++) {
    
            // Traversal from back to front 
            //j  The initial value is the total capacity of the backpack 
            for (int j = target; stones[i] <= j; j--) {
    
                //stones[i]<=j  Stone volume <= Backpack Capacity 
                //  discharge   At present j-store[i]  Capacity backpack   loading  stones[i]
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        // Subtract two stone heaps of the same size 
        return sum - dp[target] * 2;
    }

    public static void main(String[] args) {
    
        System.out.println(new LastStoneWeightII().lastStoneWeightII(new int[]{
    2, 7, 4, 1, 8, 1}));
    }
}

Code Capriccio recording brush question stopped ,xmd, I can't brush , I'm going to listen to the class and practice 55555555555