leetcode(力扣) 1049. 最後一塊石頭的重量 II (動态規劃 & 01背包問題)

文章目錄

• ​​題目描述​​
• ​​思路分析​​
• ​​完整代碼​​

題目描述

有一堆石頭，用整數數組 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

思路分析

在做這道題之前一定要先看 ​​01背包理論基礎​​

這道題難就難在如何轉化成01背包問題。

最近在練01背包，不然我是肯定想不到用背包的。

題目說讓兩個石子進行碰撞，想象一下這個過程，不斷拿兩個石頭碰撞，實際上就是分了兩個陣營，從兩個陣營A,B裡不斷拿出石子進行碰撞。

那麼問題就很簡單了，題目要求就 等于 求A,B陣營中石子大小差的最小值。

到這裡就容易想到背包了，設一個背包為A陣營，容量就是所給數組和的一半，盡量裝滿這個背包即可。B陣營直接就是總和減去A陣營就行。

老規矩 五步走：

1.确定dp下标含義：

dp[j] ：表示背包容量為j 此時能裝的最多石頭重量為dp[j]

2.确定遞推公式：

這個也很容易了，從01背包裡改一下就行。

這道題裡的 物品重量和物品價值都是等于石頭重量的。

也是兩種情況，不放這個石頭 則dp[j] = dp[j]，放這個石頭那就是dp[j-stones[i]]+stones[i] (騰出即将放進來的石頭的容量，加上他的價值)

是以：dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])

3.初始化dp數組：

這個沒啥好說的 直接是全0就行了，隻是有一點要注意，dp[j]表示背包容量為j，是以dp的長度要初始化成 總和的一半再加1。

for i in range(len(stones)):
     for j in range(target,stones[i]-1,-1):      

完整代碼

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target = sum(stones)//2
        dp = (target+1) * [0]
        for i in range(len(stones)):
            for j in range(target,stones[i]-1,-1):
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])
        return sum(stones) - dp[target] - dp[target]```