The title as follows

Each round, pick any two stones and smash them together. Suppose the stones weigh 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, then the stone weighing x will be completely crushed, and the stone weighing Y will have a new weight of Y-x. In the end, there will be no more than one stone left. Returns the minimum possible weight of this stone. If there are no stones left, 0 is returned. Example 1: input: stones = [2,7,4,1,8,1] Combine 2 and 4 to get 2, so the array becomes [2,7,1,8,1], combine 7 and 8 to get 1, so the array becomes [2,1,1], combine 2 and 1 to get 1, so the array becomes [1,1,1], combine 1 and 1 to get 0, So the array is converted to [1], which is the optimal value. Example 2: input: stones = [31,26,33,21,40] [7,2,21] [19,7,31] [12,7] [5] [2,26,21,40] [3,5,40] [2,40] output: 5 example 3: input: Stones = [1,2] Output: 1 Source: LeetCode Link: https://leetcode-cn.com/problems/last-stone-weight-ii Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Problem solving thinking as follows, using the dynamic programming, you can see a number of stones together as a great stone, stone can be divided into two groups, bumping into into two big stone, so you just need to calculate the weight of one group of how to get close to the mean (so collisions would be the minimum), which is half of all the weight and stone, Then there is the backpack problem with the capacity limit summation over 2

* ClassName: LeetCodeTest10 <br/> * Description: <br/> * date: 2021/6/9 10:11<br/> ** @author me<br/> * @since JDK 1.8 */ public class LeetCodeTest10 { A scheme where the result of a statistical calculation is equal to target. In this case, we need to find the array, and similarly, we need to add a sign (either positive or negative) to each number, and then compute the result of this expression, expecting the smallest absolute value. The problem translates to we want the target in problem 494 to be the smallest. After yesterday's analysis, just the sum of negative numbers, let's say neg, (sum -neg) + (-neg) = target <=> sum - 2 * neg = target Target = 0 <=> neg = sum/2, target = 0 <=> neg = sum/2, target = 0 <=> neg = sum/2 You can think of several stones as one big stone, and divide the small stones into two groups to become two big stones bumping into each other, so you just have to calculate how the weight of one group tends to be equal to the mean, which is half the sum of the weights of all the stones, Public static void main(String[] args) {int stones[] = {31,26,33,21,40}; int backNum = new Solution().lastStoneWeightII(stones); System.out.println(backNum); } static class Solution { public int lastStoneWeightII(int[] stones) { int sum = 0; for (int stone : stones) { sum += stone; } int val = sum / 2; Int [] dp = new int[val + 1]; For (int I = val; for (int I = val; i >= 0; i--) { if (stone <= i) { dp[i] = Math.max(dp[i], dp[i - stone] + stone); } } } //73 146-75 151 return sum - dp[val] * 2; }}}Copy the code