1049. Last Stone Weight I I

# 1049. Last Stone Weight II#

## 题目 #

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 `y`has 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`

## 题目大意 #

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

## 解题思路 #

• 给出一个数组，数组里面的元素代表的是石头的重量。现在要求两个石头对碰，如果重量相同，两个石头都消失，如果一个重一个轻，剩下的石头是两者的差值。问经过这样的多次碰撞以后，能剩下的石头的重量最轻是多少？
• 由于两两石头要发生碰撞，所以可以将整个数组可以分为两部分，如果这两部分的石头重量总和相差不大，那么经过若干次碰撞以后，剩下的石头重量一定是最小的。现在就需要找到这样两堆总重量差不多的两堆石头。这个问题就可以转化为 01 背包问题。从数组中找到 `sum/2` 重量的石头集合，如果一半能尽量达到 `sum/2`，那么另外一半和 `sum/2` 的差是最小的，最好的情况就是两堆石头的重量都是 `sum/2`，那么两两石头对碰以后最后都能消失。01 背包的经典模板可以参考第 416 题。

## 代码 #

``````
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]
}

``````

Sep 6, 2020