題目

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

中等

相關(guān)標(biāo)簽

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

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

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

最后，最多只會(huì)剩下一塊?石頭。返回此石頭?最小的可能重量?。如果沒有石頭剩下，就返回?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

思路和解題方法

使用了 0-1 背包問題的思想，通過動(dòng)態(tài)規(guī)劃的方式求解。

具體思路如下：

1. 首先，計(jì)算所有石頭的總重量?sum。
2. 然后，將問題轉(zhuǎn)化為將石頭分成兩堆，使得兩堆的重量盡可能接近?sum/2。
3. 創(chuàng)建一個(gè)大小為?15001?的動(dòng)態(tài)規(guī)劃數(shù)組?dp，用于記錄容量為?j?的背包所能裝載的最大重量。
4. 使用雙重循環(huán)遍歷石頭數(shù)組?stones?和背包容量?j，進(jìn)行動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移。
5. 在每次狀態(tài)轉(zhuǎn)移時(shí)，比較當(dāng)前背包容量?j?能夠裝載的最大重量?dp[j]?和將當(dāng)前石頭放入背包后所能得到的重量?dp[j - stones[i]] + stones[i]，取較大值更新?dp[j]。
6. 最后，返回兩堆石頭的重量差值，即?sum - dp[target] - dp[target]。

復(fù)雜度

????????時(shí)間復(fù)雜度:

????????????????O(n*m)

????????時(shí)間復(fù)雜度為 O(n * m)。

其中 n 是石頭的數(shù)量，m 是石頭總重量的一半。這是因?yàn)榇a中使用了兩層循環(huán)，外層循環(huán)遍歷石頭數(shù)組，內(nèi)層循環(huán)遍歷背包容量。對(duì)于每個(gè)背包容量，都需要進(jìn)行一次狀態(tài)轉(zhuǎn)移操作，因此總共需要進(jìn)行 n * m 次狀態(tài)轉(zhuǎn)移。

????????空間復(fù)雜度

????????????????O(m)

????????空間復(fù)雜度為 O(m)。

????????其中 m 是石頭總重量的一半。這是因?yàn)榇a中創(chuàng)建了一個(gè)大小為 15001 的動(dòng)態(tài)規(guī)劃數(shù)組 dp，用于記錄不同背包容量下的最大重量。由于背包容量的最大值為石頭總重量的一半，因此數(shù)組 dp 的大小為 m+1，即 15001。因此，所需的額外空間隨著石頭總重量的增加而增加，但是與石頭的數(shù)量無關(guān)。

需要注意的是，代碼中使用了一個(gè)固定大小的動(dòng)態(tài)規(guī)劃數(shù)組 dp，這是因?yàn)轭}目給定了石頭的最大數(shù)量為 30，每塊石頭的重量最大為 100。根據(jù)題目的限制條件，可以確定石頭總重量的上限為 3000，因此背包容量的上限為 1500。為了保證數(shù)組 dp 能夠覆蓋所有可能的背包容量，將其大小設(shè)置為 15001。如果題目的限制條件發(fā)生變化，可能需要調(diào)整數(shù)組 dp 的大小以適應(yīng)新的情況。

c++ 代碼

int lastStoneWeightII(vector<int>& stones) {
    vector<int> dp(15001, 0); // 創(chuàng)建一個(gè)大小為 15001 的動(dòng)態(tài)規(guī)劃數(shù)組 dp，初始值都為 0
    int sum = 0; // 計(jì)算所有石頭的總重量
    for (int i = 0; i < stones.size(); i++) {
        sum += stones[i];
    }
    int target = sum / 2; // 目標(biāo)是將石頭分為兩堆，使得兩堆的重量盡可能接近 sum/2

    for (int i = 0; i < stones.size(); i++) {
        for (int j = target; j >= stones[i]; j--) {
            // 動(dòng)態(tài)規(guī)劃的核心邏輯
            // dp[j] 表示容量為 j 的背包所能裝載的最大重量
            // dp[j-stones[i]]+stones[i] 表示將當(dāng)前石頭放入容量為 j 的背包中所能得到的重量
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }

    return sum - dp[target] - dp[target]; // 返回兩堆石頭的重量差值
}

簡潔寫法(使用庫函數(shù)做加法)

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001,0);
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum/2;
        for(int i = 0;i<stones.size();i++)
            for(int j = target;j>=stones[i];j--)
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
        return sum - dp[target] - dp[target];
    }
};

覺得有用的話可以點(diǎn)點(diǎn)贊，支持一下。

如果愿意的話關(guān)注一下。會(huì)對(duì)你有更多的幫助。

每天都會(huì)不定時(shí)更新哦? >人<? 。文章來源地址http://www.zghlxwxcb.cn/news/detail-741268.html

到了這里，關(guān)于力扣第1049題 最后一塊石頭的重量Il c++ 動(dòng)態(tài)規(guī)劃（01背包）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！