D40|单词拆分+多重背包

发布时间:2023年12月23日

139.单词拆分

给你一个字符串?s?和一个字符串列表?wordDict?作为字典。请你判断是否可以利用字典中出现的单词拼接出?s?。

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

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

题解复盘:

动态规划五部曲:

1)dp数组的含义(确实难想

????????dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词

2)确定递推公式

如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true

3)dp数组如何初始化

?dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

4)确定遍历顺序?

"apple", "pen" 是物品,那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。

"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的,那么我们就是强调物品之间顺序。

也就是求排列数

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

所以说,本题一定是 先遍历 背包,再遍历物品。

5)举例推导dp[i]

? ?

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !valid[i]; j++) {
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }
}

?这个版本的题解是和dp分析最符合的。


多重背包:

每个物品可使用n次,将其转换为01问题即可。

背包最大重量为10。

物品为:

重量价值数量
物品01152
物品13203
物品24302

问背包能背的物品最大价值是多少?

和如下情况有区别么?

重量价值数量
物品01151
物品01151
物品13201
物品13201
物品13201
物品24301
物品24301

毫无区别,这就转成了一个01背包问题了,且每个物品只用一次

文章来源:https://blog.csdn.net/Q77ian/article/details/135169605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。