LeetCode 1049. Weight of the last stone II daily question

Problem 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 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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/last-stone-weight-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

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

        return sum - dp[sum / 2] * 2;
    }
}