# Leetcode - Last Stone Weight II

violet posted @ May 06, 2020 05:54:31 AM in 算法 with tags Algorithm Golang DP , 259 阅读

https://leetcode.com/problems/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.
```

```func lastStoneWeightII(stones []int) int {
sum := 0
for _, s := range stones {
sum += s
}
n := len(stones)
dp := make([][]bool, sum+1)
for i := 0; i < len(dp); i++ {
dp[i] = make([]bool, n+1)
}
for i := 0; i <= n; i++ {
dp[0][i] = true
}
s := 0
for i := 1; i <= n; i++ {
for j := 1; j <= sum/2; j++ {
if dp[j][i-1] || (j >= stones[i-1] && dp[j - stones[i-1]][i-1]) {
dp[j][i] = true
if j > s {
s = j
}
}
}
}
return sum - s*2
}```

(输入验证码)
or Ctrl+Enter