本文主要是介绍代码随想录算法训练营day46 | 139.单词拆分、多重背包了解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
139.单词拆分
动态规划五部曲
- 确定dp数组及下标的含义：字符串数组为j的时候，dp[j]为true代表可以拆分为在字典中出现的单词
- 确定递推公式：if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true
- dp数组初始化：为了推导公式，dp[0] = true，其它字段都初始化为False
- 确定遍历顺序：完全背包问题(背包从小到大遍历)，排列问题(外层背包，内层物品)
- 举例推导dp
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False] * (len(s) + 1)dp[0] = Truefor j in range(1, len(s)+1):for word in wordDict:if j >= len(word) and dp[j-len(word)] and s[j-len(word):j] == word:dp[j] = Truereturn dp[-1]还有另一种写法，遍历单词时从0到背包i，有满足条件的就返回True，也挺好理解
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]多重背包了解
多重背包和01背包是非常像的，每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。
在代码中可以分摊到数组中，也可以在01背包循环中再加一个遍历
下面是C++多循环一重的代码
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < n; i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量// 以上为01背包，然后加一个遍历个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}
}这篇关于代码随想录算法训练营day46 | 139.单词拆分、多重背包了解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
