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

文檔講解：代碼隨想錄

題目鏈接：. - 力扣（LeetCode）

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

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

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

對應著01背包里的物品重量weight[i]和 物品價值value[i]。

背包的容量為所有石塊的重量的一半

盡量湊，找到背包中能裝下的最大值，

接下來進行動規五步曲：

確定dp數組以及下標的含義

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

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

相對于 01背包，本題中，石頭的重量是 stones[i]，石頭的價值也是 stones[i] ，可以 “最多可以裝的價值為 dp[j]” == “最多可以背的重量為dp[j]”

?確定遞推公式

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

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

一些同學可能看到這dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i]，看著有點暈乎。

大家可以再去看 dp[j]的含義。

dp數組如何初始化

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

因為提示中給出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。

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

當然也可以把石頭遍歷一遍，計算出石頭總重量 然后除2，得到dp數組的大小。

接下來就是如何初始化dp[j]呢，因為重量都不會是負數，所以dp[j]都初始化為0就可以了，這樣在遞歸公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不會初始值所覆蓋。

遍歷順序

倒敘遍歷

最后結果推導

最后dp[target]里是容量為target的背包所能背的最大重量。

那么分成兩堆石頭，一堆石頭的總重量是dp[target]，另一堆就是sum - dp[target]。

在計算target的時候，target = sum / 2 因為是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

那么相撞之后剩下的最小石頭重量就是 (sum - dp[target]) - dp[target]。

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:#整個石頭的重量可能不是2的倍數？，向下取整total_sum = sum(stones)target = total_sum//2dp = [0] * (target+1)for stone in stones:#注意循環的范圍for j in range(target,stone-1,-1):dp[j]  = max(dp[j],dp[j-stone]+stone)##最后的返回值為什么是這樣的return total_sum-2*dp[-1]

難點：怎么轉化為是01背包問題

補充：

• %（取模運算符）：

  • 功能：計算兩個數相除的余數。
  • 例子：7 % 3 的結果是 1，因為 7 除以 3 的余數是 1。

• /（除法運算符）：

  • 功能：計算兩個數相除的商，結果是浮點數。
  • 例子：7 / 3 的結果是 2.3333333333333335，因為 7 除以 3 是 2.333...。

• //（整數除法運算符）：

  • 功能：計算兩個數相除的商，結果是整數（向下取整）。
  • 例子：7 // 3 的結果是 2，因為 7 除以 3 是 2.333...，向下取整得到 2。

494.目標和?

文檔講解：代碼隨想錄

題目鏈接：. - 力扣（LeetCode）

?和之前的組合總和有點像，后面對比一下

放加法的是一個集合(left)，減法是一個集合(right)

left組合 - right組合 = target。

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

公式來了， left - (sum - left) = target 推導出 left = (target + sum)/2 。(如果不能整除，說明題目中沒有滿足的組合)

target是固定的，sum是固定的，left就可以求出來。

此時問題就是在集合nums中找出和為left的組合。也就是裝滿容量為left的容器有多少方法

純01背包問的是裝滿這個背包，它的最大價值是多少，分割等和子集問的是能不能裝滿這個背包，最后一塊石頭的重量是給我們一個背包，讓我們盡量去裝，而本題問的是給一個背包的容量，有多少種方法裝滿，這三道題都是01背包在不同層面上的應用

確定dp數組以及下標的含義

?dp[j]裝滿容量為j的背包有多少種方法

?確定遞推公式

有哪些來源可以推出dp[j]呢？

只要搞到nums[i]，湊成dp[j]就有dp[j - nums[i]] 種方法。

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

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

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

所以求組合類問題的公式，都是類似這種：

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

?dp數組如何初始化（不懂）

從遞推公式可以看出，在初始化的時候dp[0] 一定要初始化為1，因為dp[0]是在公式中一切遞推結果的起源，如果dp[0]是0的話，遞推結果將都是0。

這里有錄友可能認為從dp數組定義來說 dp[0] 應該是0，也有錄友認為dp[0]應該是1。

其實不要硬去解釋它的含義，咱就把 dp[0]的情況帶入本題看看應該等于多少。

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

遍歷順序

01背包倒序遍歷

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if (total_sum+target) %2 !=0 :return 0if abs(target)> total_sum:return 0left = (total_sum+target) // 2dp=[0] *(left+1) #裝滿left背包有多少方法dp[0]=1   #為什么要這樣初始化？for num in nums:for j in range(left,num-1,-1):dp[j] += dp[j-num]return dp[left]

474.一和零

?文檔講解：代碼隨想錄

題目鏈接：??????????????. - 力扣（LeetCode）

本題中strs 數組里的元素就是物品，每個物品都是一個！

而m 和 n相當于是一個背包，兩個維度的背包。

m和n就是形容一種容器，裝滿這個容器最多有多少個元素就輸出多少個

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

但本題其實是01背包問題！

只不過這個背包有兩個維度，一個是m 一個是n，而不同長度的字符串就是不同大小的待裝物品。

容器有兩個維度，物品也是有兩個維度，x個0，和y個1，重量就是[x,y]

確定dp數組以及下標的含義

二維dp數組

dp[m][n] ：裝滿m個0，n個1最多背了多少個物品

?確定遞推公式

兩個維度，放不放當前物品（x,y）

dp[i][j] = max(dp[i][j], dp[i-x][j-y] + 1)

?dp數組如何初始化

dp[0][0] = 0

非0下標也初始為0

遍歷順序

先遍歷物品，再遍歷背包，背包倒序遍歷

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0 for _ in range(n+1)] for _ in range(m+1)]#遍歷物品for str in strs:x = 0y = 0for char in str:if char == '0':x+=1else:y += 1#遍歷背包for i in range(m,x-1,-1): #存放0的個數，如果寫為0，結果會不對for j in range(n,y-1,-1):#存放1的個數dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1)return dp[m][n]