小工具知识网

当前位置: 首页 > 行业知识 > 【动态规划】代码随想录算法训练营第四十六天 |139.单词拆分,关于多重背包,你该了解这些! ,背包问题总结篇!(待补充)

行业知识

【动态规划】代码随想录算法训练营第四十六天 |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?