1049. Last Stone Weight II

Problem

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight yhas new weight y-x.

At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.

Note:

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

Problem Summary

There is a pile of stones, and the weight of each stone is a positive integer. Each round, choose any two stones from them, and then smash them together. Suppose the weights of the stones are x and y, respectively, and x <= y. Then the possible results of the smash are as follows:

If x == y, then both stones will be completely smashed; If x != y, then the stone with weight x will be completely smashed, and the stone with weight y will have a new weight of y-x. Finally, at most one stone will be left. Return the smallest possible weight of this stone. If no stone is left, return 0.

Constraints:

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

Solution Ideas

• Given an array, the elements in the array represent the weights of stones. Now we are required to smash two stones against each other. If their weights are the same, both stones disappear; if one is heavier and one is lighter, the remaining stone is the difference between the two weights. Ask what the lightest possible weight of the remaining stone is after many such collisions?
• Since stones collide in pairs, the entire array can be divided into two parts. If the total weights of the stones in these two parts do not differ much, then after several collisions, the weight of the remaining stone must be the smallest. Now we need to find two piles of stones whose total weights are about the same. This problem can be transformed into a 01 knapsack problem. Find a set of stones with weight sum/2 from the array. If one half can get as close as possible to sum/2, then the difference between the other half and sum/2 is the smallest. The best case is that the weights of the two piles of stones are both sum/2, so after pairwise collisions, they can all disappear in the end. For the classic template of 01 knapsack, refer to Problem 416.

Code

package leetcode

func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, v := range stones {
		sum += v
	}
	n, C, dp := len(stones), sum/2, make([]int, sum/2+1)
	for i := 0; i <= C; i++ {
		if stones[0] <= i {
			dp[i] = stones[0]
		} else {
			dp[i] = 0
		}
	}
	for i := 1; i < n; i++ {
		for j := C; j >= stones[i]; j-- {
			dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
		}
	}
	return sum - 2*dp[C]
}