力扣刷题day40|139单词拆分、多重背包问题总结

139. 单词拆分

力扣题目链接

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

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

示例 1：

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

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
1
2
3
4

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2

思路

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包。

因此我们先判断背包里的字符串是不是在表中，然后添加物品单词，如果已有的字符串里的单词都在词表里，新添加的词也在表里，那么就可以递归推出当前添加后的整体字符串也在词表中

动态规划五部曲

1. 确定dp数组以及下标的含义

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

2. 确定递推公式

当j < i 时，如果字符串的前面j个字符确定dp[j] 是true，且[j, i]这个区间的子串出现在字典里，那么dp[i]一定是true。

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

3. dp数组如何初始化

这里题目所说的是非空字符串s，因此当i为0是没有实际上的含义的，单纯是为了公式的推导

dp[0]是递归的根基，dp[0]一定要为true，否则递归下去后面都都是false了

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4. 确定遍历顺序

本题最终要求的是是否都出现过，那么本题使用求排列的方式，还是求组合的方式都可以。

但本题还有特殊性，因为是要求子串，最好是遍历背包放在外循环，将遍历物品放在内循环。

如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的子串都预先放在一个容器里。

所以最终这道题选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后

5. 举例推导dp[i]

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图

因为我自己在写代码的时候不是很清楚具体的过程，画图出来更加清晰了

完整代码

public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length() + 1];
    // 初始化
    dp[0] = true;

    // 将词表存入set里方便查询是否存在
    HashSet<String> set = new HashSet<>(wordDict);

    for (int j = 1; j <= s.length(); j++) { // 遍历背包
        for (int i = 0; i < j; i++) { // 遍历物品
            // 如果原来的字符串存在，且新加入的词也在词表里面
            String newStr = s.substring(i, j);
            if (dp[i] && set.contains(newStr)) {
                dp[j] = true;
            }
        }
    }

    return dp[s.length()];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

多重背包

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

思路

多重背包和01背包是非常像的，每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。因此01背包的基础上写出对应代码就可以了

例如：

背包最大重量为10。

物品为：

将背包按数量展开，物品就变成了：

这种方式来实现多重背包的代码如下：

public void testMultiPack1(){
    // 版本一：改变物品数量为01背包格式
    List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
    List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
    List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
    int bagWeight = 10;

    for (int i = 0; i < nums.size(); i++) {
        while (nums.get(i) > 1) { // 把物品展开为i
            weight.add(weight.get(i));
            value.add(value.get(i));
            nums.set(i, nums.get(i) - 1);
        }
    }

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
        }
        System.out.println(Arrays.toString(dp));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍：代码是01背包里面在加一个for循环遍历一个每种商品的数量。

public void testMultiPack2(){
    // 版本二：改变遍历个数
    int[] weight = new int[] {1, 3, 4};
    int[] value = new int[] {15, 20, 30};
    int[] nums = new int[] {2, 3, 2};
    int bagWeight = 10;

    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
            System.out.println(Arrays.toString(dp));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18