LeetCode_ 1049_ Weight of the last stone II

Topic link

• https://leetcode.cn/problems/last-stone-weight-ii/

Title Description

There is a pile of stones , Use an array of integers stones Express . among stones[i] It means the first one i The weight of a stone .

Every round , Choose from 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 piece left at most stone . Return to this stone The smallest possible weight . If there is no stone left , Just go back to 0.

Example 1：

 Input ：stones = [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 .

Example 2：

 Input ：stones = [31,26,33,21,40]
 Output ：5

Tips ：

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

Their thinking

Dynamic programming

Try to divide the stones into two equal piles , The stones left after the collision are the smallest , Therefore, it is converted into 01 knapsack problem

Dynamic programming five steps

• determine dp The meaning of array and subscript
  • dp[j]: Capacity of j The backpack , You can recite at most dp[j] Heavy stone
• Determine the recurrence formula
  • stay 01 In the backpack , The recurrence formula is dp[j] = Math.max(dp[j],dp[j-weight[i] + value[i]]),dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i])
• dp Array initialization
  • dp[0] = 0, Other subscripts dp[i] = 0
• Determine the traversal order
  • Traversal of items for Loop on the outer layer , Traversing the backpack for Loop on the inner layer , And inner for Loop backward traversal
• For example, push to dp Array
  • Finally, it is divided into two piles of stones , The total weight of a pile is dp[bagWeight], The other pile is sum - dp[bagWeight]
  • So finally back to sum - dp[bagWeight] * 2

AC Code

class Solution {
    
    public int lastStoneWeightII(int[] stones) {
    
        int sum = 0;
        for (int i : stones) {
    
            sum += i;
        }
        int bagWeight = sum / 2;
        int[] dp = new int[bagWeight + 1];
        dp[0] = 0;
        for (int i = 0; i < stones.length; i++) {
    
            for (int j = bagWeight; j >= stones[i]; j--) {
    
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[bagWeight] * 2;
    }
}