第九章 動態規劃
- 139.單詞拆分
- 代碼隨想錄文章詳解
- 總結
139.單詞拆分
dp[i]表示字符串的前i個字符能被拆分為字典中的單詞
排列問題：外循環背包，內循環物品
字符串能被字典拆分，將當前字符串s[:i]拆分為s[:j]和s[j:i]，意味著s[:j]能被字典拆分，且s[j:i]在字典中存在
一邊擴展背包邊界，一邊用字典試探能否滿足拆分要求
func wordBreak(s string, wordDict []string) bool {wordSet := make(map[string]bool)for _, word := range wordDict {wordSet[word] = true}n := len(s)dp := make([]bool, n+1)dp[0] = truefor i := 0; i <= n; i++ {for j := 0; j < i; j++ {word := s[j:i]dp[i] = dp[i] || dp[j] && wordSet[word]}}return dp[n]
}
代碼隨想錄文章詳解
139.單詞拆分
關于多重背包，你該了解這些
背包問題總結篇！
總結
1、0/1背包：外循環nums,內循環target,target倒序且target從nums[i]開始
| 題目 | 類型 | 轉移方程 |
|---|---|---|
| 416.分割等和子集 | 存在問題(bool) | dp[i] = dp[i] || dp[i-num] |
| 1049.最后一塊石頭的重量II | 最值問題 | dp[i] = max(dp[i], dp[i-num]+nums) |
| 474.一和零 | 最值問題 | dp[i] = max(dp[i], dp[i-nums]+1) |
| 494.目標和 | 組合問題 | dp[i] += dp[i-num] |
2、完全背包：
(1)求總和嵌套循環內外順序不影響
外循環nums,內循環target,target正序且target從nums[i]開始
外循環target,內循環nums,target正序且target>=nums[i]
| 題目 | 類型 | 轉移方程 |
|---|---|---|
| 322.零錢兌換 | 最值問題 | dp[i] = min(dp[i], dp[i-nums]+1) |
| 279.完全平方數 | 最值問題 | dp[i] = min(dp[i], dp[i-j*j]+1) |
(2)求組合數、排列數內外循環需注意
求組合數：外層for遍歷物品，內層for遍歷背包。
求排列數：外層for遍歷背包，內層for遍歷物品。
| 題目 | 類型 | 轉移方程 |
|---|---|---|
| 518.零錢兌換II | 組合問題 | dp[i] += dp[i-num] |
| 377.組合總和Ⅳ | 排列問題 | dp[i] += dp[i-num] |
| 139.單詞拆分 | 排列問題 | dp[i] = dp[i] || dp[j] && wordSet[s[j:i]] |
