行业知识
【动态规划】代码随想录算法训练营第四十六天 |139.单词拆分,关于多重背包,你该了解这些! ,背包问题总结篇!(待补充)
2026-11-19 01:16:31
来源:互联网转载
139.单词拆分
1、题���链接:. - 力扣(LeetCode)
2、文章讲解:代码随想录
3、题目:
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:
- 输入: s = "leetcode", wordDict = ["leet", "code"]
- 输出: true
- 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2:
- 输入: s = "applepenapple", wordDict = ["apple", "pen"]
- 输出: true
- 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
- 注意你可以重复使用字典中的单词。
示例 3:
- 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
- 输出: false
4、视频链接:
动态规划之完全背包,你的背包如何装满?| LeetCode:139.单词拆分_哔哩哔哩_bilibili
class Solution { public boolean wordBreak(String s, List wordDict) { HashSet set = new HashSet(wordDict); boolean[] valid = new boolean[s.length() + 1]; valid[0] = true; for (int i = 1; i > bagWeight >> n; vector weight(n, 0); vector value(n, 0); vector nums(n, 0); for (int i = 0; i > weight[i]; for (int i = 0; i > value[i]; for (int i = 0; i > nums[i]; for (int i = 0; i 1) { // 物品数量不是一的,都展开 weight.push_back(weight[i]); value.push_back(value[i]); nums[i]--; } } vector dp(bagWeight + 1, 0); for(int i = 0; i = weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout > bagWeight >> n; vector weight(n, 0); vector value(n, 0); vector nums(n, 0); for (int i = 0; i > weight[i]; for (int i = 0; i > value[i]; for (int i = 0; i > nums[i]; vector dp(bagWeight + 1, 0); for(int i = 0; i = weight[i]; j--) { // 遍历背包容量 // 以上为01背包,然后加一个遍历个数 for (int k = 1; k = 0; k++) { // 遍历个数 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]); } } } cout
上一篇:aws服务器怎么选?
下一篇:如何安装winpe?