算法訓練營day38 動態規劃⑥ 322. 零錢兌換、279.完全平方數、139.單詞拆分、多重背包

????????動態規劃的第六篇！背包問題總結篇！

322. 零錢兌換

????????題目中說每種硬幣的數量是無限的，可以看出是典型的完全背包問題。但是如何找最小的“組合”呢？（通過dp數組的不同定義與遞推公式）

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

????????dp[j]：湊足總額為j所需錢幣的最少個數為dp[j]

確定遞推公式

????????湊足總額為j - coins[i]的最少個數為dp[j - coins[i]]，那么只需要加上一個錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]

????????遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

dp數組如何初始化

????????首先湊足總金額為0所需錢幣的個數一定是0，那么dp[0] = 0;

????????其他下標對應的數值呢？考慮到遞推公式的特性，dp[j]必須初始化為一個最大的數，否則就會在min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。

確定遍歷順序

????????本題求錢幣最小個數，那么錢幣有順序和沒有順序都可以，都不影響錢幣的最小個數。

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。
如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

舉例推導dp數組

????????略

????????以先遍歷物品、后遍歷背包為例

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1)  # 創建動態規劃數組，初始值為正無窮大dp[0] = 0  # 初始化背包容量為0時的最小硬幣數量為0for coin in coins:  # 遍歷硬幣列表，相當于遍歷物品for i in range(coin, amount + 1):  # 遍歷背包容量# 注意這個for循環的“剪枝”if dp[i - coin] != float('inf'):  # 如果dp[i - coin]不是初始值，則進行狀態轉移dp[i] = min(dp[i - coin] + 1, dp[i])  # 更新最小硬幣數量if dp[amount] == float('inf'):  # 如果最終背包容量的最小硬幣數量仍為正無窮大，表示無解return -1return dp[amount]  # 返回背包容量為amount時的最小硬幣數量

279.完全平方數

????????題目翻譯一下：完全平方數就是物品（可以無限件使用），湊個正整數n就是背包，問湊滿這個背包最少有多少物品？

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

????????dp[j]：和為j的完全平方數的最少數量為dp[j]

確定遞推公式

????????dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以湊成dp[j]。

????????此時我們要選擇最小的dp[j]，所以遞推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

dp數組如何初始化

????????dp[0]表示和為0的完全平方數的最小數量，那么dp[0]一定是0。

????????從遞歸公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要選最小的，所以非0下標的dp[j]一定要初始為最大值，這樣dp[j]在遞推的時候才不會被初始值覆蓋。

確定遍歷順序

????????最小組合，和上題一樣

????????所以本題外層for遍歷背包，內層for遍歷物品，還是外層for遍歷物品，內層for遍歷背包，都是可以的！

舉例推導dp數組

????????略

class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1):  # 遍歷背包for j in range(1, int(i ** 0.5) + 1):  # 遍歷物品 # 注意對j的取值范圍進行開根號的限制# 更新湊成數字 i 所需的最少完全平方數數量dp[i] = min(dp[i], dp[i - j * j] + 1)# 注意這個位置使用的是j * jreturn dp[n]

139.單詞拆分

動態規劃

????????單詞就是物品，字符串s就是背包，單詞能否組成字符串s，就是問物品能不能把背包裝滿。

拆分時可以重復使用字典中的單詞，說明就是一個完全背包！

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

????????dp[i] : 字符串長度為i的話，dp[i]為true，表示可以拆分為一個或多個在字典中出現的單詞。

確定遞推公式

????????如果確定dp[j] 是true，且 [j, i] 這個區間的子串出現在字典里，那么dp[i]一定是true。（j < i ）。

????????所以遞推公式是 if([j, i] 這個區間的子串出現在字典里 && dp[j]是true) 那么 dp[i] = true。

dp數組如何初始化

????????從遞推公式中可以看出，dp[i] 的狀態依靠 dp[j]是否為true，那么dp[0]就是遞推的根基，dp[0]一定要為true，否則遞推下去后面都都是false了。

確定遍歷順序

????????拿 s = "applepenapple", wordDict = ["apple", "pen"] 舉例。

????????"apple", "pen" 是物品，那么我們要求物品的組合一定是 "apple" + "pen" + "apple" 才能組成 "applepenapple"。

????????"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我們就是強調物品之間順序。

????????所以說，本題一定是先遍歷背包，再遍歷物品。

????????換而言之，就是題目中的字符串中單詞元素可能出現在多個位置，所以不能先遍歷物品，不然物品就被消耗掉了，按序遍歷到后面就沒有物品可用了

舉例推導dp[i]

????????略

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)n = len(s)dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 個字符是否可以被拆分成單詞dp[0] = True  # 初始狀態，空字符串可以被拆分成單詞for i in range(1, n + 1): # 遍歷背包for j in range(i): # 遍歷單詞if dp[j] and s[j:i] in wordSet:dp[i] = True  # 如果 s[0:j] 可以被拆分成單詞，并且 s[j:i] 在單詞集合中存在，則 s[0:i] 可以被拆分成單詞# 防止被覆蓋breakreturn dp[n]

回溯解法

遞歸終止條件

if startIndex >= len(s):return True

遞歸邏輯

從 startIndex 開始，嘗試所有可能的拆分位置 i
截取從 startIndex 到 i 的子串作為候選單詞
如果這個候選單詞在字典中存在，并且從 i+1 位置開始的剩余字符串也能被成功拆分（遞歸調用的結果為 True），則返回 True

class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:# 邊界情況：已經遍歷到字符串末尾，返回Trueif startIndex >= len(s):return True# 遍歷所有可能的拆分位置for i in range(startIndex, len(s)):word = s[startIndex:i + 1]  # 截取子串if word in wordSet and self.backtracking(s, wordSet, i + 1):# 如果截取的子串在字典中，并且后續部分也可以被拆分成單詞，返回Truereturn True# 無法進行有效拆分，返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)  # 轉換為哈希集合，提高查找效率return self.backtracking(s, wordSet, 0)

多重背包（了解即可）

????????之前我們學了01背包、完全背包，現在我們來看一下多重背包的概念和題目

56. 攜帶礦石資源（第八期模擬筆試）

????????多重背包和01背包是非常像的，為什么和01背包像呢？每件物品最多有Mi件可用，把Mi件攤開，其實就是一個01背包問題了。

C, N = input().split(" ")
C, N = int(C), int(N)# value數組需要判斷一下非空不然過不了
weights = [int(x) for x in input().split(" ")]
values = [int(x) for x in input().split(" ") if x]
nums = [int(x) for x in input().split(" ")]dp = [0] * (C + 1)
# 遍歷背包容量
for i in range(N):for j in range(C, weights[i] - 1, -1):for k in range(1, nums[i] + 1):# 遍歷 k，如果已經大于背包容量直接跳出循環if k * weights[i] > j:breakdp[j] = max(dp[j], dp[j - weights[i] * k] + values[i] * k) 
print(dp[-1])