LeetCode 139.单词拆分
LeetCode 多重背包
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。 dp[0] = true, 下标非0的dp[i]初始化为false 而本题其实我们求的是排列数，为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。 “apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。 “apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。 所以说，本题一定是 先遍历 背包，再遍历物品。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 0; i <= s.length(); i++) {
for (String word : wordDict) {
int len = word.length();
if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
class Solution {
public boolean wordBreak(String s, List<String> 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; j++) {
if (wordDict.contains(s.substring(j, i)) && valid[j]) {
valid[i] = true;
}
}
}
return valid[s.length()];
}
}
对于回溯法需要再复习
多重背包
相当于每种商品遍历的个数放在01背包里面在遍历一遍。 k
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int bs = sc.nextInt();
int len = sc.nextInt();
int[] weight = new int[len];
int[] value = new int[len];
int[] num = new int[len];
for (int i = 0; i < len; i++) {
weight[i] = sc.nextInt();
}
for (int i = 0; i < len; i++) {
value[i] = sc.nextInt();
}
for (int i = 0; i < len; i++) {
num[i] = sc.nextInt();
}
int[] dp = new int[bs + 1];
for (int i = 0; i < len; i++) {
for (int j = bs; j >= weight[i]; j--) {
for (int k = 1; k <= num[i] && k * weight[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
}
}
}
System.out.println(dp[bs]);
}
}
背包总结
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);问装满背包有几种方法：dp[j] += dp[j - nums[i]];问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
01背包
二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。 完全背包
纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。如果求最小数，那么两层for循环的先后顺序就无所谓了
