目錄

DAY42

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

解題思路&代碼

494.目標(biāo)和

解題思路&代碼

474.一和零

解題思路&代碼

---

DAY42

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

力扣題目鏈接(opens new window)

題目難度：中等

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

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

如果?x == y，那么兩塊石頭都會(huì)被完全粉碎；

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

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

解題思路&代碼

思路：

關(guān)鍵點(diǎn)：認(rèn)識(shí)到什么是應(yīng)用類背包問(wèn)題，此處如何聯(lián)系到背包？盡量把容器分成大小相等的兩堆，則另一堆是否能用數(shù)組元素填滿多少則是涉及到了背包最多能裝多少的問(wèn)題

本題其實(shí)就是盡量讓石頭分成重量相同的兩堆，相撞之后剩下的石頭最小，這樣就化解成01背包問(wèn)題了。

是不是感覺和昨天講解的416. 分割等和子集?(opens new window)非常像了。

本題物品的重量為stones[i]，物品的價(jià)值也為stones[i]。

對(duì)應(yīng)著01背包里的物品重量weight[i]和 物品價(jià)值value[i]。

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

dp[j]表示容量（這里說(shuō)容量更形象，其實(shí)就是重量）為j的背包，最多可以背最大重量為dp[j]。

可以回憶一下01背包中，dp[j]的含義，容量為j的背包，最多可以裝的價(jià)值為 dp[j]。

2.確定遞推公式

01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本題則是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

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

既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石頭的重量和。

因?yàn)樘崾局薪o出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。

而我們要求的target其實(shí)只是最大重量的一半，所以dp數(shù)組開到15000大小就可以了

4.確定遍歷順序

在動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些！（滾動(dòng)數(shù)組）?(opens new window)中就已經(jīng)說(shuō)明：如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷！

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

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp數(shù)組int[] dp = new int[target + 1];//為什么要+1，因?yàn)樯婕暗奖嘲亓繛?的情況，要初始化，但是實(shí)際上數(shù)組元素是不包括這個(gè)的for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//兩種情況，要么放，要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}

494.目標(biāo)和

力扣題目鏈接(opens new window)

難度：中等

給定一個(gè)非負(fù)整數(shù)數(shù)組，a1, a2, ..., an, 和一個(gè)目標(biāo)數(shù)，S?，F(xiàn)在你有兩個(gè)符號(hào)?+?和?-。對(duì)于數(shù)組中的任意一個(gè)整數(shù)，你都可以從?+?或?-中選擇一個(gè)符號(hào)添加在前面。

返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。

示例：

• 輸入：nums: [1, 1, 1, 1, 1], S: 3
• 輸出：5

解釋：

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

一共有5種方法讓最終目標(biāo)和為3。

?

解題思路&代碼

思路：

本題要如何使表達(dá)式結(jié)果為target，

既然為target，那么就一定有 left組合 - right組合 = target。

left + right = sum，而sum是固定的。right = sum - left

公式來(lái)了， left - (sum - left) = target 推導(dǎo)出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出來(lái)。

此時(shí)問(wèn)題就是在集合nums中找出和為left的組合

再回歸到01背包問(wèn)題，為什么是01背包呢？

因?yàn)槊總€(gè)物品（題目中的1）只用一次！

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

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

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

dp[j] 表示：填滿j（包括j）這么大容積的包，有dp[j]種方法

其實(shí)也可以使用二維dp數(shù)組來(lái)求解本題，dp[i][j]：使用 下標(biāo)為[0, i]的nums[i]能夠湊滿j（包括j）這么大容量的包，有dp[i][j]種方法。

2.確定遞推公式

有哪些來(lái)源可以推出dp[j]呢？

只要搞到nums[i]，湊成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)。

所以求組合類問(wèn)題的公式，都是類似這種：

dp[j] += dp[j - nums[i]]

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

從遞推公式可以看出，在初始化的時(shí)候dp[0] 一定要初始化為1，因?yàn)閐p[0]是在公式中一切遞推結(jié)果的起源，如果dp[0]是0的話，遞推結(jié)果將都是0。

如果數(shù)組[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0。 dp[0]也應(yīng)該是1， 也就是說(shuō)給數(shù)組里的元素 0 前面無(wú)論放加法還是減法，都是 1 種方法。

所以本題我們應(yīng)該初始化 dp[0] 為 1。

4.確定遍歷順序

在動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些！（滾動(dòng)數(shù)組）?(opens new window)中，我們講過(guò)對(duì)于01背包問(wèn)題一維dp的遍歷，nums放在外循環(huán)，target在內(nèi)循環(huán)，且內(nèi)循環(huán)倒序。

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

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

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

dp數(shù)組狀態(tài)變化如下：

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

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target的絕對(duì)值大于sum，那么是沒(méi)有方案的if (Math.abs(target) > sum) return 0;//如果(target+sum)除以2的余數(shù)不為0，也是沒(méi)有方案的if ((target + sum) % 2 == 1) return 0;int bagSize = (target + sum) / 2;int[] dp = new int[bagSize + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
}

474.一和零

力扣題目鏈接(opens new window)

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

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

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

示例 1：

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

• 輸出：4

• 解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因?yàn)樗?4 個(gè) 1 ，大于 n 的值 3 。

解題思路&代碼

思路：

本題并不是多重背包，再來(lái)看一下這個(gè)圖，捋清幾種背包的關(guān)系

多重背包是每個(gè)物品，數(shù)量不同的情況。

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

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

理解成多重背包的同學(xué)主要是把m和n混淆為物品了，感覺這是不同數(shù)量的物品，所以以為是多重背包。

但本題其實(shí)是01背包問(wèn)題！

只不過(guò)這個(gè)背包有兩個(gè)維度，一個(gè)是m 一個(gè)是n，而不同長(zhǎng)度的字符串就是不同大小的待裝物品。

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ù)組如何初始化

在動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些！（滾動(dòng)數(shù)組）?(opens new window)中已經(jīng)講解了，01背包的dp數(shù)組初始化為0就可以。

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

4.確定遍歷順序

在動(dòng)態(tài)規(guī)劃：關(guān)于01背包問(wèn)題，你該了解這些！（滾動(dòng)數(shù)組）?(opens new window)中，我們講到了01背包為什么一定是外層for循環(huán)遍歷物品，內(nèi)層for循環(huán)遍歷背包容量且從后向前遍歷！

那么本題也是，物品就是strs里的字符串，背包容量就是題目描述中的m和n。

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

class Solution {public int findMaxForm(String[] strs, int m, int n) {//dp[i][j]表示i個(gè)0和j個(gè)1時(shí)的最大子集int[][] dp = new int[m + 1][n + 1];int oneNum, zeroNum;for (String str : strs) {//正序遍歷物品oneNum = 0;zeroNum = 0;for (char ch : str.toCharArray()) {if (ch == '0') {zeroNum++;} else {oneNum++;}}//倒序遍歷背包容量for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}