本文主要是介绍代码随想录算法训练营|day46,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
第九章 动态规划
- 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 := 1; i <= n; i++ {for j := 0; j < i; j++ {if dp[j] && wordSet[s[j:i]]{dp[i] = truebreak}}}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[j] && wordSet[s[j:i]] |
这篇关于代码随想录算法训练营|day46的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!