行业知识
代码随想录算法训练营第四十六天 139.单词拆分、多重背包（了解）、 背包总结
2026-11-01 22:26:48
来源：互联网转载
代码随想录算法训练营第四十六天 | 139.单词拆分、多重背包（了解）、 背包总结
139.单词拆分
题���链接：139. 单词拆分 - 力扣（LeetCode）
class Solution { public boolean wordBreak(String s, List wordDict) { // 字典中的单词就是物品，字符串s就是背包，物品能不能把背包装满？ Set wordDictSet = new HashSet(wordDict); boolean[] dp = new boolean[s.length() + 1]; // dp[i]表示字符串 s 前 i个字符组成的字符串 s[0..i−1]是否能被空格拆分成若干个字典中出现的单词 // 递推公式 // if( [j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。 dp[0] = true; // dp[0]就是递推的根基，dp[0]一定要为true， dp[0]没有意义 // 先遍历背包 /** 如果求组合数就是外层for循环遍历物品，内层for遍历背包。 如果求排列数就是外层for遍历背包，内层for循环遍历物品。 ✔ */ for(int i = 1; i // 然后，我们开始遍历字符串 "leetcode" 的每个字符，同时对于每个字符，我们都会从字符头部遍历到当前字符的每个子字符串。 for(int j = 0; j
