单词拆分这道题，我的思路是字符串看做背包容量，单词作为物品，字符串由单词组成，并且单词可以重复使用，因此可以看做是一道完全背包。这时候需要考虑dp[]的含义了。题目问的是字符串能否由单词构成，所以把dp[i]定义成i容量的背包（i长度的字符串）能否由可单词组成，是个boolean类型。dp[0] = true，初始化表示，字符串长度为0时，那么就可以由一个单词数组构成（不使用任何单词）。dp[i] = true的条件是，（1）字符串切割[0，i)（前闭后开），判断这段字符串能否由单词组成。（2）如果字符串切割[（i- 单词长度）， i)（前闭后开）是单词数组中的一个单词，并且dp[i -单词长度 ]也是true，说明剩下的字符串也可以由其他单词组成。满足这两个条件的，其实就说明这个字符串可以由单词组成。具体可以看代码进行理解

139. 单词拆分

给你一个字符串 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
提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

      

class Solution {public boolean wordBreak(String s, List<String> wordDict) {int len = s.length();//存放单词，方便切割字符串判断是否等于单词Set<String> set = new HashSet<>(wordDict);boolean[] dp = new boolean[len + 1];dp[0] = true;for(int i = 1; i <= len; i++){for(int j = 0; j < wordDict.size(); j++){//背包容量大于等于单词长度if(i >= wordDict.get(j).length()){//切割的字符串在单词里面找的到     || 切割的部分字符串在单词找的到，并且剩下的字符串是trueif( set.contains(s.substring(0, i)) || (set.contains(s.substring(i - wordDict.get(j).length(), i)) && dp[i - wordDict.get(j).length()]) ){dp[i] = true;}}               }}return dp[len];}
}

多重背包
对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

重量    价值    数量
物品0    1    15    2
物品1    3    20    3
物品2    4    30    2
问背包能背的物品最大价值是多少？

和如下情况有区别么？

重量    价值    数量
物品0    1    15    1
物品0    1    15    1
物品1    3    20    1
物品1    3    20    1
物品1    3    20    1
物品2    4    30    1
物品2    4    30    1
毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
————————————————
版权声明：本文为CSDN博主「石头走到哪里还是石头」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_46516575/article/details/129948393