目錄：

解題及思路學(xué)習(xí)

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

思考：要剩下的石頭盡可能重量小，所以就是背包的重量盡可能接近總值的一半。

隨想錄：

1、dp[j] 表示背包容量為j的最大價(jià)值dp[j]. 本題中價(jià)值等于重量，所以也就是最大重量dp[j].

2、dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ? dp[j] = max(dp[j], dp[j-stone[i]] + ston[i]);

3、初始化。dp[0] = 0, 非零下標(biāo)初始化為0.

4、確定遍歷順序。第一層for循環(huán)遍歷的是物品，第二層for循環(huán)遍歷的是背包。為了保證所有物品只放了一次，所以是從大到小去遍歷。（如果從小大遍歷就是完全背包了）

5、舉例推導(dǎo)dp數(shù)組

舉例，輸入：[2,4,1,1]，此時(shí)target = (2 + 4 + 1 + 1)/2 = 4 ，dp數(shù)組狀態(tài)圖如下：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-2apHXva6-1688570040937)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/b43630c5-e46b-43c0-b83f-c12a514651db/Untitled.png)]

代碼：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        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];
    }
};

• 時(shí)間復(fù)雜度：O(m × n) , m是石頭總重量（準(zhǔn)確的說(shuō)是總重量的一半），n為石頭塊數(shù)
• 空間復(fù)雜度：O(m)

這道題dp的定義很關(guān)鍵，是容量為j的時(shí)候，所能裝的最大價(jià)值（重量）。注意容量不一定都要用完j。

494. 目標(biāo)和

https://leetcode.cn/problems/target-sum/

給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?target?。

向數(shù)組中的每個(gè)整數(shù)前添加?'+'?或?'-'?，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè)?表達(dá)式?：

• 例如，nums = [2, 1]?，可以在?2?之前添加?'+'?，在?1?之前添加?'-'?，然后串聯(lián)起來(lái)得到表達(dá)式?"+2-1"?。

返回可以通過(guò)上述方法構(gòu)造的、運(yùn)算結(jié)果等于?target?的不同?表達(dá)式?的數(shù)目。

示例 1：

輸入：nums = [1,1,1,1,1], target = 3
輸出：5

思考：思不開(kāi)，想不到。

隨想錄：nums里面的數(shù)組可以分為正數(shù)類(lèi)集合（left) 和負(fù)數(shù)類(lèi)集合 (right) 。那么有→

left + right = sum , left - right = target. ? left = (sum + target) /2;

當(dāng) (sum + target) 不能整除2的時(shí)候，說(shuō)明不滿足條件，返回0。 再dp過(guò)程中要盡量能夠是正數(shù)這個(gè)集合（背包）裝滿。本題相當(dāng)于是給我們一個(gè)背包容量，有多少種方式能把背包裝滿。此時(shí)問(wèn)題就轉(zhuǎn)化為，裝滿容量為x的背包，有幾種方法。

這次和之前遇到的背包問(wèn)題不一樣了，之前都是求容量為j的背包，最多能裝多少。

本題則是裝滿有幾種方法。其實(shí)這就是一個(gè)組合問(wèn)題了。

1、dp[j] 裝滿背包容量為j ， 有dp[j]種方法。

2、dp[j] += dp[j-nums[i]]。

例如：dp[j]，j 為5，

• 已經(jīng)有一個(gè)1（nums[i]） 的話，有 dp[4]種方法 湊成 容量為5的背包。
• 已經(jīng)有一個(gè)2（nums[i]） 的話，有 dp[3]種方法 湊成 容量為5的背包。
• 已經(jīng)有一個(gè)3（nums[i]） 的話，有 dp[2]中方法 湊成 容量為5的背包
• 已經(jīng)有一個(gè)4（nums[i]） 的話，有 dp[1]中方法 湊成 容量為5的背包
• 已經(jīng)有一個(gè)5 （nums[i]）的話，有 dp[0]中方法 湊成 容量為5的背包

那么湊整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起來(lái)。

3、dp[0] = 1; 非零下標(biāo)初始化為0.

4、遍歷順序。第一層遍歷物品，第二層遍歷背包。倒序。

5、舉例推導(dǎo)dp數(shù)組

輸入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-Le1tJjWa-1688570040941)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2fae4be7-6fe7-4f58-a02f-21ede6495323/Untitled.png)]

代碼：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此時(shí)沒(méi)有方案
        if ((S + sum) % 2 == 1) return 0; // 此時(shí)沒(méi)有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

• 時(shí)間復(fù)雜度：O(n × m)，n為正數(shù)個(gè)數(shù)，m為背包容量
• 空間復(fù)雜度：O(m)，m為背包容量

個(gè)人感覺(jué)上面的遞推公式那里有一定的誤導(dǎo)性。幾個(gè)nums[i] 會(huì)讓人覺(jué)得只跟nums[i] 的個(gè)數(shù)有關(guān)，但其實(shí)是和nums[i]中的數(shù)值有關(guān)。如果例如nums[i] 是2的話，那么dp[j] += dp[j-2] 。給的例子中只是因?yàn)槎际?這種巧合。 所以應(yīng)該是： 背包容量已經(jīng)有了2的話， 那么剩下j-2 容量，所以是dp[j-2]種填滿方法。

474.一和零

https://leetcode.cn/problems/ones-and-zeroes/

給你一個(gè)二進(jìn)制字符串?dāng)?shù)組?strs?和兩個(gè)整數(shù)?m?和?n?。

請(qǐng)你找出并返回?strs?的最大子集的長(zhǎng)度，該子集中?最多?有?m?個(gè)?0?和?n?個(gè)?1?。

如果?x?的所有元素也是?y?的元素，集合?x?是集合?y?的?子集?。

示例 1：

輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4

思考：最大子集，感覺(jué)是要填兩個(gè)背包m和n。填這兩個(gè)背包種記錄一個(gè)最大子集長(zhǎng)度。

隨想錄：要裝滿m和0，n個(gè)1這么大容器的背包，這個(gè)背包里面最多有多少個(gè)物品。

本題中strs 數(shù)組里的元素就是物品，每個(gè)物品都是一個(gè)！

而m 和 n相當(dāng)于是一個(gè)背包，兩個(gè)維度的背包。

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

   dp[i][j]：最多有i個(gè)0和j個(gè)1的strs的最大子集的大小為dp[i][j]。

2. 確定遞推公式

   dp[i][j] 可以由前一個(gè)strs里的字符串推導(dǎo)出來(lái)，strs里的字符串有zeroNum個(gè)0，oneNum個(gè)1。

   dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

   然后我們?cè)诒闅v的過(guò)程中，取dp[i][j]的最大值。

   所以遞推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

   此時(shí)大家可以回想一下01背包的遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

   對(duì)比一下就會(huì)發(fā)現(xiàn)，字符串的zeroNum和oneNum相當(dāng)于物品的重量（weight[i]），字符串本身的個(gè)數(shù)相當(dāng)于物品的價(jià)值（value[i]）。

   這就是一個(gè)典型的01背包！?只不過(guò)物品的重量有了兩個(gè)維度而已。

3. dp數(shù)組如何初始化

   01背包的dp數(shù)組初始化為0就可以。

   因?yàn)槲锲穬r(jià)值不會(huì)是負(fù)數(shù)，初始為0，保證遞推的時(shí)候dp[i][j]不會(huì)被初始值覆蓋。

4. 確定遍歷順序

   外層for循環(huán)遍歷物品，內(nèi)層for循環(huán)遍歷背包容量且從后向前遍歷！

5. 舉例推導(dǎo)數(shù)組

   以輸入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3為例

   最后dp數(shù)組的狀態(tài)如下所示：

   [外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-vSq8a5GR-1688570040943)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c563df54-a1a7-49bf-a001-3f6555d9eef8/Untitled.png)]

代碼：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默認(rèn)初始化0
        for (string str : strs) { // 遍歷物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

• 時(shí)間復(fù)雜度: O(kmn)，k 為strs的長(zhǎng)度
• 空間復(fù)雜度: O(mn)

知識(shí)點(diǎn)記錄

知識(shí)點(diǎn)

此時(shí)我們講解了0-1背包的多種應(yīng)用，

• **純 0 - 1 背包?(opens new window)**是求 給定背包容量 裝滿背包 的最大價(jià)值是多少。
• **416. 分割等和子集?(opens new window)**是求 給定背包容量，能不能裝滿這個(gè)背包。
• **1049. 最后一塊石頭的重量 II?(opens new window)**是求 給定背包容量，盡可能裝，最多能裝多少
• **494. 目標(biāo)和?(opens new window)**是求 給定背包容量，裝滿背包有多少種方法。
• 本題是求 給定背包容量，裝滿背包最多有多少個(gè)物品。

以上是0-1背包不同維度上的應(yīng)用。

個(gè)人反思

背包問(wèn)題，好復(fù)雜！

上述應(yīng)該把0-1背包常見(jiàn)的問(wèn)題給總結(jié)了?？梢远嗳パ芯恳幌逻@幾道題，多看幾遍體會(huì)一下。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-524623.html

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