★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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: 1Explanation: 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

---

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]输出：1解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

提示：

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

---

Runtime: 40 ms

Memory Usage: 20.9 MB

1 class Solution { 2     let MAX:Int = 3005 3     func lastStoneWeightII(_ stones: [Int]) -> Int { 4         var possible:[Bool] = [Bool](repeating:false,count:2 * MAX + 1) 5         possible[MAX] = true 6         for stone in stones 7         { 8             var next_possible:[Bool] = [Bool](repeating:false,count:2 * MAX + 1) 9             for x in 0...2 * MAX10             {11                 if possible[x]12                 {13                     14                     next_possible[x + stone] = true15                     next_possible[x - stone] = true16                 }17             }18             possible = next_possible19         }20         for i in 0...MAX21         {22             if possible[MAX + i]23             {24                 return i25             }26         }27         return -1        28     }29 }