難度：★★★☆☆
類型：數(shù)組
方法：動(dòng)態(tài)規(guī)劃

題目

力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄

有一堆石頭，每塊石頭的重量都是正整數(shù)。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

如果 x == y，那么兩塊石頭都會(huì)被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。
最后，最多只會(huì)剩下一塊石頭。返回此石頭最小的可能重量。如果沒有石頭剩下，就返回 0。

示例：

輸入：[2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

解答

這道題是零一背包問題的變體，我們先看動(dòng)態(tài)規(guī)劃解決零一背包問題。

零一背包

問題是這樣的。有一個(gè)背包，最多能裝物品重量為capacity，有n個(gè)物品，重量和價(jià)值分別在列表weights和values中，問如何能讓這個(gè)背包裝價(jià)值最多的物品。

【數(shù)組定義】

定義數(shù)組dp，維度是(n+1)×(capacity+1)，dp[i][j]表示，背包最多載重量為j時(shí)，前i個(gè)物品作為備選物品可以裝得的最大價(jià)值。

【初始化】

背包最多能裝的重量是零時(shí)，顯然說明這個(gè)包什么也不能裝，總價(jià)值自然是零，把第一行填充為零。

如果物品數(shù)量為零時(shí)，說明這個(gè)包沒有可以裝的東西，總價(jià)值自然是零，把第一列填充為零。

【遞推公式】

為了獲得dp[i][j]，我們自然要著重研究i位置對(duì)應(yīng)的物品，這里需要注意，dp的下標(biāo)和weights的下標(biāo)之間是正好錯(cuò)開1的，所以i位置對(duì)應(yīng)的物品重量和價(jià)格實(shí)際上是weights[i-1]，values[i-1]，我們姑且稱為weight,value。

首先把dp[i][j]的值從dp[i-1][j]繼承過來，也就是不裝當(dāng)前物品weight的情況。接下來，就要考慮到底是不是要把當(dāng)前物品weight加入到包裹中了。

這里需要有一個(gè)判斷，既然當(dāng)前dp[i][j]位置包的容量為j，首先就要看看，這個(gè)物品本身weight是否已經(jīng)超過了包的荷載量，如果沒有超過，則說明該物品是有這個(gè)潛力加入到包裹中的。其實(shí)我們并不用管現(xiàn)在包裹里面有啥，只需要考慮，之前的所有包裹weights[:i]，在荷載量為j-weight時(shí)，可以最多裝多少價(jià)值東西，如果加上當(dāng)前物品，可以超過之前的價(jià)值dp[i-1][j-weight]，則加入，否則不加入。因此有一個(gè)判斷：dp[i][j] = max(dp[i][j], dp[i-1][j-weight] + value)，當(dāng)然這是要在當(dāng)前物品weight不超過包裹容積j的前提下討論的。

【返回值】

最終，我們只關(guān)心，所有i個(gè)包裹在荷載量為capacity時(shí)最多可以裝的東西，正好對(duì)應(yīng)的dp數(shù)組中的dp[-1][-1]，把該數(shù)值返回即可。

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]

回到這道題

我們可以把石頭分成總重量盡可能接近的兩個(gè)陣營(yíng)，這樣，兩個(gè)陣營(yíng)的石頭碰撞（一個(gè)陣營(yíng)的石頭只能碰另一個(gè)陣營(yíng)的石頭），最終只剩一個(gè)石頭時(shí)候，它的重量一定是最小的。讀者如果不相信，可以自行找?guī)讉€(gè)石頭碰一下。

問題就轉(zhuǎn)化為，如何能夠選一些石頭，這些石頭的總重量盡可能接近所有石頭總量的一半half。石頭重量組成列表為stones，我們有個(gè)荷載量為half的包裹，問重量為stones，價(jià)值也為stones的一堆物品怎么裝能夠使得價(jià)值最大化，這就跟我們上面講述的01背包問題成為一回事了。

注意一下函數(shù)返回值，這兩個(gè)陣營(yíng)的石頭，各自損失的量都是dp[-1][-1]，因此最后返回值應(yīng)該是總重量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]

當(dāng)然，我們可以通過一些方式減小空間復(fù)雜度。

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]

如有疑問或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析