Leetcode Link: 1049. 最后一块石头的重量 II - 力扣（LeetCode）
题目
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回0。
解法一
自己的思路 1：从暴力递归到动态规划
思路： 仔细理解题目，题目可以认为等价于：
将输入的
stone的分成两组，输出两组和的差的最小值。
由于 stone 是固定的，因此一组大另一组一定小，所以实际上可以通过计算其中一组距离 target = sum(stone)/2 距离再乘2来求得两组的最小差
那么我们的问题进一步转化成：
从输入的
stone挑出一些石头，让这些石头的和距离target最小（即01背包问题，stone就是物品，target就差不多是我们的背包容量，但是我们实际上是可以超过背包容量的，我们要的是最小差）
那么，我们的子问题是给定当前位置 idx, 当前总和 ssum, 我们需要构造一个函数，该函数返回的是从 idx 到最后位置上的石头里，距离target的最小值
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
target = sum(stones) / 2
res = self.process(stones, target, 0, 0)
return int(2*res)
# [idx .. n] 中距离 target 的最小值
# 前面的不考虑了，就知道前面的和为ssum
def process (self, stones, target, idx, ssum):
# base case: 石头都已经挑没了
# 注意此时 idx 已经越界了
if idx == len(stones):
return abs(ssum-target)
## 分成两种情况，pick当前位置的石头，不pick当前位置的石头
p1 = self.process(stones, target, idx+1, ssum)
p2 = self.process(stones, target, idx+1, ssum+stones[idx])
return min(p1, p2)根据上面的暴力递归，改写成动态规划
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total_sum = sum(stones)
target = total_sum / 2
# [行 idx， 列 total sum+1]
dp = [[0 for _ in range (total_sum)] for _ in range (len(stones)+1)]
# 根据 base case 设置初始值
for ss in range(total_sum):
dp[len(stones)][ss] = abs (ss - target)
# 根据依赖分别填写其他的值
# 这里可以看看下面的笔记，有一点小弯
for i in range(len(stones)-1, -1, -1):
for j in range(total_sum):
if not 0 <= (j+stones[i]) < total_sum:
dp[i][j] = dp[i+1][j] # 这一步实际上暴力递归中没有体现，是debug出来的
else:
dp[i][j] = min(dp[i+1][j], dp[i+1][j+stones[i]])
return int(2*dp[0][0])本思路中的弯弯绕
- 暴力递归中，我们的 base case 是
idx==len(stones)，显然这个时候，idx 已经越界了，因此需要在动态规划中将 dp 的行数设置成len(stones)+1- 基于 1，我们在通过 base case 进行初始值的填写的时候也要相应的注意，这一点和经典的 dp 有点区别（经典的 dp 一般行数就是
len(stones)）- 相比于暴力递归，动态规划的版本多出来一个越界的判断，这是在暴力递归中没有体现的，而是通过debug补上的，这里的弯弯绕不好。该判断说明的是，当
j+stones[i]值比total_sum还大的时候，距离target值一定不会是j+stones[i]，因为他已经比total sum还大，而我们能从表里取到的值dp[i+1][j]一定小于total sum
由于上述思路存在诸多的弊端，我尝试向 01 背包的解题模式靠近，
即子问题返回的是从[idx.. n]中，剩余的值的最小值
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
target = sum(stones) / 2
res = self.process(stones, target, 0, target)
return int(2*res)
# [idx .. n] abs(rest) 的最小值
# 等价于距离 target 的最小
def process (self, stones, target, idx, rest):
# 3个base case
if rest == 0: # 1. ==0 肯定最小，直接返回
return 0
if rest < 0: # 小于零肯定不用再继续了，因为都是正数，只能更小，所以直接返回 abs(rest)
return abs(rest)
if idx == len(stones): # 当越界的时候，也直接返回了
return abs(rest)
p1 = self.process(stones, target, idx+1, rest) # 不要 idx
p2 = self.process(stones, target, idx+1, rest-stones[idx]) # 要 idx
return min(p1, p2)然而，该思路在变成动态规划时，是有更严重的问题的。下面我贴出转化后的代码，来分析为什么这个转成动态规划的代码是错误的
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total_sum = sum(stones)
target = total_sum // 2
dp = [[0 for _ in range(target)] for _ in range(len(stones)+1)] # [idx, rest]
for i in range(len(stones)+1):
dp[i][0] == 0
for i in range(target):
dp[len(stones)][i] = abs(i)
for i in range(len(stones)-1, -1, -1):
for j in range(target):
if not 0 <= (j-stones[i]) < target:
dp[i][j] = min(dp[i+1][j], abs(j-stones[i]))
else:
dp[i][j] = min(dp[i+1][j], dp[i+1][j-stones[i]])
return int(2*dp[0][target-1])问题
- 实际上我们依然没能解决行的长度为
len(stones)+1的逻辑不一致性- 列数变成了
target，然而 target 有可能是 0.5 的小数，这样是不能直接in range(target)的，这就导致了我们的算法一定会在这个思路上出错，除非进一步处理一下- 然而稍微好点的是我们在两个for里的越界判断是可以体现在暴力递归中的，但是由于本方法不能直接转dp，故也没辙~
代码随想录中似乎是采用的本思路，然而是直接套的01背包模板，后面可以熟悉看看。