昨天，我初步掌握了 0/1 背包問題的理論基礎和標準解法。今天，我將這種思想應用到了更廣泛的場景中。今天的幾道題，乍一看和背包沒什么關系，但通過巧妙的數學轉化，它們的核心都變成了 0/1 背包問題。

這讓我深刻體會到，學習算法不僅僅是學習模板，更重要的是學習一種建模能力——將一個看似全新的問題，轉化為我們熟悉的模型來求解。為了加深理解，我對每個適用的問題都同時實現了二維和一維的解法，以觀察它們之間的聯系和區別。

一、實戰演練：識別偽裝的背包問題

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

題目描述: 有一堆石頭，用整數數組 stones 表示。其中 stones[i] 是第 i 塊石頭的重量。每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎…最后，最多只會剩下一塊石頭。返回此石頭最小的可能重量。

• 學習感悟: 這個問題等價于將所有石頭分成兩堆 A 和 B，并讓它們的重量差 |sum(A) - sum(B)| 最小。為了實現這一點，我們需要讓其中一堆的重量 sum(A) 盡可能地接近總重量的一半。這完美地轉化為了一個 0/1 背包問題：

  • 背包容量: target = total_sum // 2
  • 物品: stones 數組中的每一個 stone
  • 物品重量/價值: stone 的重量
  • 目標: 在容量為 target 的背包里，能裝下的最大重量是多少？
    

• 資源包:
  * 題目/文章: https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
  * 視頻講解: https://www.bilibili.com/video/BV14M411C7oV

我的實現 1：二維 DP

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total_sum = sum(stones)target = total_sum // 2n = len(stones)# dp[i][j]: 從0..i-1號石頭中任選，放入容量j的背包，能達到的最大重量dp = [[0] * (target + 1) for _ in range(n + 1)]for i in range(1, n + 1):stone_weight = stones[i - 1]for j in range(target + 1):if j < stone_weight:dp[i][j] = dp[i - 1][j] # 裝不下，不裝else:# 裝或者不裝dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stone_weight] + stone_weight)sum_A = dp[n][target]sum_B = total_sum - sum_Areturn sum_B - sum_A

我的實現 2：一維 DP (空間優化)

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:total_sum = sum(stones)target = total_sum // 2# dp[j]：容量為j的背包，能裝下的最大重量dp = [0] * (target + 1)for stone_weight in stones:# 倒序遍歷，保證每個石頭只用一次for j in range(target, stone_weight - 1, -1):dp[j] = max(dp[j], stone_weight + dp[j - stone_weight])sum_A = dp[target]sum_B = total_sum - sum_Areturn sum_B - sum_A

2. LeetCode 494. 目標和

題目描述: 給你一個整數數組 nums 和一個整數 target 。向數組中的每個整數前添加 '+' 或 '-'。返回可以通過上述方法構造的、運算結果等于 target 的不同表達式的數目。

• 學習感悟: 這道題是計數型 DP，但同樣可以轉化為背包問題。假設加 + 的子集和為 P，加 - 的子集和為 N。我們有 P - N = target 和 P + N = total_sum。兩式相加得 2P = target + total_sum，即 P = (target + total_sum) / 2。
  • 背包模型: 問題變成了：從 nums 中挑選出一些數，使其和恰好為 new_target = (target + total_sum) / 2，共有多少種挑法？
  • DP 定義: dp[j] 表示和為 j 的組合有多少種。
• 資源包:
  • 題目/文章: https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
  • 視頻講解: https://www.bilibili.com/video/BV1o8411j73x

我的實現 1：二維 DP

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if abs(target) > total_sum or (total_sum + target) % 2 != 0:return 0new_target = (total_sum + target) // 2n = len(nums)# dp[i][j]: 從0..i-1號數中任選，和為j的組合數dp = [[0] * (new_target + 1) for _ in range(n + 1)]dp[0][0] = 1 # 用0個數湊成和為0，有一種方法（什么都不選）for i in range(1, n + 1):num = nums[i - 1]for j in range(new_target + 1):if j < num:dp[i][j] = dp[i - 1][j] # 不選numelse:# 組合數 = (不選num的方法數) + (選num的方法數)dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]return dp[n][new_target]

我的實現 2：一維 DP (空間優化)

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)if abs(target) > total_sum or (total_sum + target) % 2 != 0:return 0new_target = (total_sum + target) // 2# dp[j]：和為 j 的組合有多少種dp = [0] * (new_target + 1)dp[0] = 1for num in nums:# 倒序遍歷，保證每個數只用一次for j in range(new_target, num - 1, -1):dp[j] += dp[j - num]return dp[new_target]

3. LeetCode 474. 一和零

題目描述: 給你一個二進制字符串數組 strs 和兩個整數 m 和 n 。請你找出 strs 的最大子集的長度，該子集中 最多 有 m 個 0 和 n 個 1 。

• 學習感悟: 這道題是二維費用的 0/1 背包，是背包問題的一個重要變種。

  • 背包容量: 是一個二維的 (m, n)，分別代表 0 和 1 的容量。
  • 物品: strs 數組中的每個字符串。
  • 物品重量: 每個字符串的重量也是二維的 (count_zeros, count_ones)。
  • 物品價值: 每個字符串價值都是 1。

• DP 定義: dp[i][j] 表示用 i 個 0 和 j 個 1 能構成的最大子集長度。

• 狀態轉移: dp[i][j] = max(dp[i][j], 1 + dp[i - count_zeros][j - count_ones])。

• 遍歷順序: 因為是 0/1 背包，兩個表示容量的循環 i 和 j 都必須倒序遍歷。

• 資源包:

  • 題目/文章: https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
  • 視頻講解: https://www.bilibili.com/video/BV1rW4y1x7ZQ

我的實現：二維費用背包

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:# dp[i][j]：用 i 個 0 和 j 個 1 能構成的最大子集長度dp = [[0] * (n + 1) for _ in range(m + 1)]for s in strs: # 遍歷物品count_zeros = s.count('0')count_ones = s.count('1')# 倒序遍歷背包的兩個維度容量for i in range(m, count_zeros - 1, -1):for j in range(n, count_ones - 1, -1):dp[i][j] = max(dp[i][j], 1 + dp[i - count_zeros][j - count_ones])return dp[m][n]

總結

今天我更深刻地理解了 0/1 背包問題的泛用性。它不僅僅是一個求最大價值的模型，通過改變 dp 數組的定義（求最大重量、求組合數、求可行性）和狀態轉移的方式，它可以解決各種各樣的問題。識別問題背后的背包模型，并正確地進行轉化，是解決這類 DP 問題的關鍵所在。從一維費用到二維費用，背包問題的世界真是廣闊。