↓Skip to main content
  1. Posts/

LeetCode-1049 最后一块石头的重量 II

·1 min·
Table of Contents

LeetCode-1049 最后一块石头的重量 II #

Solution 1 #

粉碎石头的过程可以等价为在 $stones[i]$ 前面添加 $+$ 或者 $-$, 找出一个最小的非负和. 计所有石头重量之和为 $total$ , 添加负号的石头重量之和为 $neg$ , 则结果为 $total - 2neg$ , 转化为: 挑选重量和不超过 $\lfloor \frac{total}{2}\rfloor$ 的最大重量, 这是一个背包问题. 定义 $dp[i][j]$ 为前 $i$ 块石头能否凑出重量 $j$ , 有状态转移方程: $$ dp[i][j] = \begin{cases} dp[i - 1][j],\ if\ stones[i - 1] < j\ \max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]]),\ otherwise \end{cases} $$ 找出使得 $dp[n][j] = 1$ 最大的 $j$ , 答案即为 $total - 2j$ . 代码如下:

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        total = sum(stones)
        bag = total // 2
        
        dp = [[0 for _ in range(bag + 1)] for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for j in range(bag + 1):
                if stones[i - 1] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]])
        
        res = 0
        for j in range(bag, -1, -1):
            if dp[n][j]:
                res = j
                break
        return total - 2 * res