代码随想录算法训练营第四十六天|139.单词拆分、背包问题总结

代码随想录算法训练营第四十六天|139.单词拆分、背包问题总结

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
1
2
3

题解：单词的组成是有顺序的，所以是一个完全背包的排列问题

• 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数组

代码：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

背包问题总结：

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需要从小到大

​ 组合问题：先物品后背包

​ 排列问题：先背包后物品