难度：★★★☆☆
类型：数组
方法：动态规划
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 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 <= stones.length <= 30
1 <= stones[i] <= 1000
解答
这道题是零一背包问题的变体，我们先看动态规划解决零一背包问题。
零一背包
问题是这样的。有一个背包，最多能装物品重量为capacity，有n个物品，重量和价值分别在列表weights和values中，问如何能让这个背包装价值最多的物品。
【数组定义】
定义数组dp，维度是(n+1)×(capacity+1)，dp[i][j]表示，背包最多载重量为j时，前i个物品作为备选物品可以装得的最大价值。
【初始化】
背包最多能装的重量是零时，显然说明这个包什么也不能装，总价值自然是零，把第一行填充为零。
如果物品数量为零时，说明这个包没有可以装的东西，总价值自然是零，把第一列填充为零。
【递推公式】
为了获得dp[i][j]，我们自然要着重研究i位置对应的物品，这里需要注意，dp的下标和weights的下标之间是正好错开1的，所以i位置对应的物品重量和价格实际上是weights[i-1]，values[i-1]，我们姑且称为weight,value。
首先把dp[i][j]的值从dp[i-1][j]继承过来，也就是不装当前物品weight的情况。接下来，就要考虑到底是不是要把当前物品weight加入到包裹中了。
这里需要有一个判断，既然当前dp[i][j]位置包的容量为j，首先就要看看，这个物品本身weight是否已经超过了包的荷载量，如果没有超过，则说明该物品是有这个潜力加入到包裹中的。其实我们并不用管现在包裹里面有啥，只需要考虑，之前的所有包裹weights[:i]，在荷载量为j-weight时，可以最多装多少价值东西，如果加上当前物品，可以超过之前的价值dp[i-1][j-weight]，则加入，否则不加入。因此有一个判断：dp[i][j] = max(dp[i][j], dp[i-1][j-weight] + value)，当然这是要在当前物品weight不超过包裹容积j的前提下讨论的。
【返回值】
最终，我们只关心，所有i个包裹在荷载量为capacity时最多可以装的东西，正好对应的dp数组中的dp[-1][-1]，把该数值返回即可。
from typing import List
class Solution:
def bag01(self, weights: List[int], values: List[int], capacity:int) -> int:
n = len(weights)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n+1):
weight, value = weights[i-1], values[i-1]
for j in range(1, capacity+1):
dp[i][j] = dp[i-1][j]
if j >= weight:
dp[i][j] = max(dp[i][j], dp[i-1][j-weight] + value)
return dp[-1][-1]
回到这道题
我们可以把石头分成总重量尽可能接近的两个阵营，这样，两个阵营的石头碰撞（一个阵营的石头只能碰另一个阵营的石头），最终只剩一个石头时候，它的重量一定是最小的。读者如果不相信，可以自行找几个石头碰一下。
问题就转化为，如何能够选一些石头，这些石头的总重量尽可能接近所有石头总量的一半half。石头重量组成列表为stones，我们有个荷载量为half的包裹，问重量为stones，价值也为stones的一堆物品怎么装能够使得价值最大化，这就跟我们上面讲述的01背包问题成为一回事了。
注意一下函数返回值，这两个阵营的石头，各自损失的量都是dp[-1][-1]，因此最后返回值应该是总重量total - 2 * dp[-1][-1]。
from typing import List
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
n = len(stones)
half = total // 2
dp = [[0 for _ in range(half + 1)] for _ in range(n + 1)]
for i in range(1, n+1):
stone = stones[i-1]
for j in range(1, half+1):
dp[i][j] = dp[i-1][j]
if j >= stone:
dp[i][j] = max(dp[i][j], dp[i-1][j-stone] + stone)
return total - 2 * dp[-1][-1]
当然，我们可以通过一些方式减小空间复杂度。
from typing import List
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
half = total // 2
dp = [0] * (half + 1)
for stone in stones:
for i in reversed(range(stone, len(dp))):
dp[i] = max(dp[i], dp[i - stone] + stone)
return total - 2 * dp[half]
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
