代码随想录二刷day46

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、力扣139. 单词拆分

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 i = 1; i <= s.length(); i ++){for(int j = 0; j < i && !dp[i]; j ++){if(dp[j] && set.contains(s.substring(j,i))){dp[i] = true;}}}return dp[dp.length-1];}
}

二、力扣动态规划：关于多重背包，你该了解这些！

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) { // 把物品展开为iweight.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));}
}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));}}
}