1049. 最后一块石头的重量 II

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/last-stone-weight-ii/
Star
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [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]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
示例 3：
输入：stones = [1,2]
输出：1
提示：
  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

法1 动态规划 二维dp

思路
本题目其实是要将石头尽可能的均为为两等份，然后看差值
状态定义：dp[i][j]：在nums[0:i]中， 组成不超过j的最大石头重量
状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]]+nums[i-1]) 。分别为 使用不当前数字的最大重量，使用当前数字的最大重量
初始化：为0即可
题解
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 其实是要将石头尽可能的均为为两等份，然后看剩下的重量
        sum_ = sum(stones)
        target = sum_ // 2
        # 在nums[0:i]中， 组成不超过j的最大石头重量
        dp = [[0]*(target+1) for _ in range(len(stones)+1)]
        
        for i in range(1, len(stones)+1):
            for j in range(0, target+1):
                # 当前容量太小了，放不下stone[i-1]
                if j - stones[i-1] < 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1])

        return sum_ - dp[-1][target]*2

法2 动态规划 一维dp

思路
dp[i] 只取决于 dp[i-1]
题解
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target = sum(stones) // 2

        # 在stones[:i]中挑选， 容量为 j 的背包最多装多少重量的石头
        dp = [0] * (target+1) 
        
        for i in range(1, len(stones)+1):
            temp = [0] * (target+1) 
            for j in range(0, target+1):
                temp[j] = dp[j]
                if j - stones[i-1] >= 0:
                    temp[j] = max(temp[j], dp[j-stones[i-1]] + stones[i-1])
            dp = temp
        return sum(stones) - dp[-1] * 2