---

139.單詞拆分

題目鏈接

思路

1. 確定dp數組以及下標的含義
   dp[i] : 從0開始長度為i的字符串是否可以拆分為一個或多個在字典中出現的單詞
2. 確定遞推公式
   如果確定dp[j] 是true，且 [j, i] 這個區間的子串出現在字典里，那么dp[i]一定是true。（j < i ）。
   遞推公式是 if([j, i] 這個區間的子串出現在字典里 && dp[j]是true)
3. dp數組如何初始化
   dp[0]一定要為true，否則遞推下去后面都都是false了。下標非0的dp[i]初始化為false
4. 確定遍歷順序
   本題其實我們求的是排列數。
   拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 舉例：
   “apple”, “pen” 是物品，那么我們要求 物品的組合一定是 “apple” + “pen” + “apple” 才能組成 “applepenapple”。
   “apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我們就是強調物品之間順序。
   所以說，本題一定是先遍歷背包，再遍歷物品。
5. 舉例推導dp[i]

代碼實現

有一個困惑點，為什么不能用wordSet.size()而必須用s.size()

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {   // 遍歷背包for (int j = 0; j < i; j++) {       // 遍歷物品string word = s.substr(j, i - j); //substr(起始位置，截取的個數)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};

---

背包問題總結

背包類型

1. 01背包
   有限個種類數的物品，每個只有一個，裝在有限個單一背包里
   一維數組基本上都是外層背包內層物品，外層循環從前到后遍歷，內層循環從后向前遍歷，以防重復計算
   對應題目：
   等和分割子串
   最后一塊石頭的重量 II
   目標和
   一和零：這道題是二維的問題，有點抽象
2. 完全背包
   有限個種類數的物品，每個有無數個，裝在有限個單一背包里
   組合問題一般外層循環是物品，遍歷順序從前到后；內層循環是背包，遍歷順序從前到后
   排列問題一般外層循環是背包，遍歷順序從前到后；內層循環是物品，遍歷順序從前到后
   對應題目：
   組合問題：零錢兌換II
   排列問題：組合總和 Ⅳ、爬樓梯、零錢兌換、完全平方數、??單詞拆分：這道題看不太出可以用動態規劃，但是把字符串長度看成背包，字符串內單詞看成物品，也可以用動態規劃方法來解決，因為我們最后想得到的結果只是一個bool值，內部單詞順序不同對答案有影響，所以是個排列問題
3. 多重背包
   有限個種類數的物品，每個有多個，裝在有限個單一背包里
   其實把它轉化為01背包就好了。
   如下圖的要求：
   
   轉化為01背包則為：
   

遞推公式

問能否能裝滿背包（或者最多裝多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);，對應題目如下：
等和分割子串
最后一塊石頭的重量 II
問裝滿背包有幾種方法：dp[j] += dp[j - nums[i]] ，對應題目如下：
零錢兌換II
目標和
組合總和 Ⅳ
爬樓梯
問背包裝滿最大價值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，對應題目如下：
一和零
問裝滿背包所有物品的最小個數：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，對應題目如下：
零錢兌換
完全平方數