代码随想录算法训练营第四十六天|139.单词拆分、背包问题总结
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
题解：单词的组成是有顺序的，所以是一个完全背包的排列问题
-
dp[i] : 长度为 i 的字符串是否能被字典中的单词组成的结果是 dp[i]
-
递推公式 ：dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
-
初始化：0下标初始化为true ，非零下标初始化为 false(因为还不知道能不能由字典中的单词组成)
-
遍历顺序：排列问题，先背包后物品
-
打印dp数组
代码：
java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set=new HashSet<>(wordDict);boolean [] dp=new boolean[s.length()+1];dp[0]=true;for(int j=1;j<=s.length();j++){ //背包for(int i=0;i<j && !dp[j];i++){ //物品if(set.contains(s.substring(i,j)) && dp[i]){dp[j]=true;}}}return dp[s.length()];}
}
背包问题总结：
1、背包的递推公式：
- 能否装满（最大能装多少）：dp[j]=max(dp[j],dp[j-numd[i]]+nums[i])
- 装满有几种方法：dp[j]+=dp[j-nums[i]]
- 背包的最大价值 ：dp[j]=man(dp[j],dp[j-weight[i]]+value[i])
- 装满背包的最小个数：dp[j]=min(dp[j],dp[j-coins[i]]+1)
2、遍历顺序
- 01背包：
二维：物品和背包先遍历哪个都可以，第二个for要从小到大
一维：只能先物品后背包，且第二层for 需要从大到小（确保每个物品只被取一次）
- 完全背包：
纯背包问题的一维dp实现，先遍历物品还是先遍历背包都可以，第二层for需要从小到大
组合问题：先物品后背包
排列问题：先背包后物品
