1049. 最后一塊石頭的重量 II

一、題目

有一堆石頭，用整數(shù)數(shù)組 stones 表示。其中 stones[i] 表示第 i 塊石頭的重量。

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

• 如果 x == y，那么兩塊石頭都會(huì)被完全粉碎；
• 如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會(huì)剩下一塊 石頭。返回此石頭 最小的可能重量 。如果沒(méi)有石頭剩下，就返回 0。

示例 1：

輸入：stones = [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)值。

示例 2：

輸入：stones = [31,26,33,21,40]
輸出：5

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

二、題解

方法一：01背包二維數(shù)組

算法思路

01背包問(wèn)題回顧

在01背包問(wèn)題中，我們有一組物品，每個(gè)物品有兩個(gè)屬性：重量和價(jià)值。背包有一個(gè)固定的容量，我們的目標(biāo)是在不超過(guò)背包容量的情況下，選擇物品放入背包，使得放入的物品總價(jià)值最大。

我們可以將這個(gè)問(wèn)題的狀態(tài)定義為 dp[i][j]，表示在前 i 個(gè)物品中，背包容量為 j 的情況下，可以獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程可以表示為：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

將題目映射到01背包

現(xiàn)在我們回到題目中，雖然題目描述中沒(méi)有直接提到背包，但我們可以通過(guò)觀察發(fā)現(xiàn)類似的特性：我們要將石頭分成兩堆，使得兩堆的重量差盡量小。

在01背包問(wèn)題中，我們選擇物品放入背包的狀態(tài)是離散的：要么放入，要么不放入。在本題中，我們可以類比，將石頭看作是我們要選擇放入背包的“物品”，每塊石頭的重量看作是物品的“重量”。我們要將石頭分成兩堆，使得兩堆的重量差盡量小，相當(dāng)于在一個(gè)背包的容量為總重量的一半時(shí)，選擇一些石頭放入背包，使得背包中的石頭總重量盡量接近總重量的一半。

（這里的背包容量就對(duì)應(yīng)著總重量的一半，而每塊石頭的重量和價(jià)值相同）。這就是為什么我們能夠?qū)⑦@個(gè)問(wèn)題映射到01背包問(wèn)題。

具體實(shí)現(xiàn)

1. 狀態(tài)定義： 定義一個(gè)二維數(shù)組 dp[i][j]，表示在前 i 塊石頭中，能否找到一種分法，使得其中一組的總重量恰好為 j。這里 i 的范圍是從 0 到石頭的總數(shù)，j 的范圍是從 0 到總重量的一半（因?yàn)槲覀円獙⑹^分成兩組，兩組的重量和不能超過(guò)總重量的一半，否則不符合題意）。

2. 狀態(tài)轉(zhuǎn)移： 對(duì)于每一塊石頭，我們可以選擇將其放入其中一組，或者不放入。如果我們不放入第 i 塊石頭，那么問(wèn)題就轉(zhuǎn)化為在前 i-1 塊石頭中尋找一種分法，使得其中一組的總重量恰好為 j。如果我們放入第 i 塊石頭，那么問(wèn)題就轉(zhuǎn)化為在前 i-1 塊石頭中尋找一種分法，使得其中一組的總重量恰好為 j - stones[i]。

   綜合考慮這兩種情況，我們可以得到狀態(tài)轉(zhuǎn)移方程：

   dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]]
   

3. 邊界條件： 初始化時(shí)，當(dāng)只有一塊石頭可選時(shí)，如果這塊石頭的重量不超過(guò) j，那么我們可以將其放入其中一組，否則不放入。

4. 最終結(jié)果： 最終的答案應(yīng)該是在所有可能的總重量 j 中，找到最大的 j，使得 dp[n-1][j] 為 true（n 為石頭的總數(shù)）。然后最小可能的剩余重量就是 sum - 2 * j。

根據(jù)上述思路，可以實(shí)現(xiàn)出解題代碼：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }
        
        int n = stones.size();
        vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));
        
        // 初始化
        for (int i = 0; i <= sum / 2; i++) {
            if (stones[0] <= i) {
                dp[0][i] = stones[0];
            }
        }
        
        // 填寫dp數(shù)組
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= sum / 2; j++) {
                if (stones[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                }
            }
        }
        
        return sum - 2 * dp[n - 1][sum / 2];
    }
};

方法二：01背包一維數(shù)組

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }
        
        vector<int> dp(sum/2+1, 0);
        // 填寫dp數(shù)組
        for (int i = 0; i < stones.size(); i++) {
            for (int j = sum/2; j >= stones[i]; j--) {  
                dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
            }        
        }
        return sum - 2 * dp[sum/2];
    }
};

Q：為什么 for (int j = sum/2; j >= stones[i]; j–)要倒序遍歷？

A：我們從前往后遍歷石頭，同時(shí)從總重量的一半開始遞減遍歷，這是因?yàn)槲覀兿朐谔顚?dp[j] 時(shí)，基于之前的狀態(tài) dp[j-stones[i]] 進(jìn)行更新。如果我們從小到大遍歷 j，那么在填寫 dp[j] 時(shí)，我們可能會(huì)使用當(dāng)前石頭的重量（stones[i]），而這就會(huì)導(dǎo)致重復(fù)使用同一塊石頭，與題意不符。

所以，倒序遍歷 j 可以確保在填寫 dp[j] 時(shí)，我們只會(huì)考慮之前的狀態(tài)，而不會(huì)用到當(dāng)前石頭。這是為了避免在填寫 dp[j] 時(shí)，使用當(dāng)前石頭導(dǎo)致重復(fù)計(jì)算的情況。

Q：為什么一定要先遍歷石頭重量這一行然后遍歷重量那一列？

A：這是為了確保狀態(tài)轉(zhuǎn)移方程的正確性。讓我們通過(guò)一個(gè)例子來(lái)理解。

假設(shè)我們有以下石頭的重量：stones = [2, 7, 4]。

我們想要使用動(dòng)態(tài)規(guī)劃找到一種分法，使得其中一組的總重量盡量接近總重量的一半。在此例中，總重量是 2 + 7 + 4 = 13，所以我們希望找到一種分法，使得其中一組的重量接近 13 / 2 = 6。

現(xiàn)在，假設(shè)先遍歷重量（j），再遍歷石頭（i)。在這種情況下，第一次遍歷（j = sum/2，i從0到stones.size()）后我們的動(dòng)態(tài)規(guī)劃狀態(tài)數(shù)組如下所示：

stones = [2, 7, 4]
dp[i][j]:
         0   1   2   3   4   5   6      
  2:     0   0   0   0   0   0   4      
  7:     0   0   0   0   0   0   4      
  4:     0   0   0   0   0   0   4      

在這種遍歷順序下，最后一列一直到最后都不會(huì)再更新了，顯然是一個(gè)錯(cuò)誤的遍歷順序。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-686926.html

到了這里，關(guān)于LeetCode1049. 最后一塊石頭的重量 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！