代码随想录算法训练营第四十四天 | 322. 零钱兑换、279.完全平方数、139.单词拆分、多重背包理论基础、背包问题总结

322. 零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/
文档讲解：https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
视频讲解：https://www.bilibili.com/video/BV14K411R7yv/

思路

• 确定dp数组以及下标的含义：凑成金额j最少需要dp[j]个硬币。
• 确定递推公式：dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);。需要注意的是只有dp[j - coins[i]]不为初始值时才进行计算，不然没有意义。
• dp数组如何初始化：因为求的是最小值，所以初始化为Integer.MAX_VALUE，dp[0] = 0;，凑成0元需要0个硬币。
• 确定遍历顺序：因为是求最小值且硬币个数无限，所以正序遍历背包和物品，谁先遍历都可以。
• 打印dp数组，用于debug

代码

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];for (int i = 0; i <= amount; i++) dp[i] = Integer.MAX_VALUE;dp[0] = 0;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要if (dp[j - coins[i]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

分析：时间复杂度：O(mn)，空间复杂度：O(m)。m是amount的值，n是coins的长度。

279.完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/
文档讲解：https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
视频讲解：https://www.bilibili.com/video/BV12P411T7Br/

思路

• 确定dp数组以及下标的含义：和为j的完全平方数最小个数为dp[j]。
• 确定递推公式：dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
• dp数组如何初始化：因为是求最小值，所以初始化为最大值，和为0的完全平方数个数为0。

for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;
dp[0] = 0;

• 确定遍历顺序：因为是求最小值且硬币个数无限，所以正序遍历背包和物品，谁先遍历都可以。
• 打印dp数组，用于debug

代码

我的代码

class Solution {public int numSquares(int n) {int[] nums = new int[n];int numslen = 0;// 先得到小于n的完全平方数都有哪些，存入数组，作为物品。for (int i = 1; i * i <= n; i++) {nums[numslen++] = i * i;}int[] dp = new int[n + 1];for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;dp[0] = 0;for (int i = 0; i < numslen; i++) {for (int j = nums[i]; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);}}return dp[n];}
}

卡哥代码

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];for (int j = 0; j <= n; j++) {dp[j] = Integer.MAX_VALU;}dp[0] = 0;for (int i = 1; i * i <= n; i++) {for (int j = i * i; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}

分析：时间复杂度：O(n * √n)，空间复杂度：O(n)。

139.单词拆分

题目链接：https://leetcode.cn/problems/word-break/
文档讲解：https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html
视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh/

思路

• 确定dp数组以及下标的含义：字符串长度为j的话，dp[j]为true，表示可以拆分为一个或多个在字典中出现的单词。
• 确定递推公式：如果确定dp[i] 是true，且 [i, j] 这个区间的子串出现在字典里，那么dp[j]一定是true。所以递推公式是 if (hash.contains(s.substring(i, j)) && dp[i]) dp[j] = true;。
• dp数组如何初始化：Arrays.fill(dp, false);，dp[0] = true;
• 确定遍历顺序：本题其实我们求的是排列数，为什么呢。 拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。
  apple，pen是物品，那么我们要求物品的组合一定是 apple + pen + apple 才能组成 applepenapple。
  apple + apple`` + pen或者pen+apple+apple` 是不可以的，那么我们就是强调物品之间顺序。
  所以说，本题一定是先遍历背包，再遍历物品。
• 打印dp数组，用于debug

代码

class Solution {public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> hash = new HashSet<>(wordDict); // 转换成hash表，能快速判断是否单词存在在字典里boolean[] dp = new boolean[s.length() + 1];Arrays.fill(dp, false);dp[0] = true;for (int j = 1; j <= s.length(); j++) {  // 遍历背包for (int i = 0; i < j && !dp[j]; i++) { // 遍历物品if (hash.contains(s.substring(i, j)) && dp[i]) dp[j] = true;}}return dp[s.length()];}
}

分析：时间复杂度：O(n³)，空间复杂度：O(n)。因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）。

多重背包理论基础

题目链接：https://kamacoder.com/problempage.php?pid=1066
文档讲解：https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F…

思路

将多重背包中多个物品的数量展开，然后看做是01背包来解决。

代码

import java.util.Scanner;public class Main{public static void main(String [] args) {Scanner sc = new Scanner(System.in);int bagWeight = sc.nextInt();int n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] nums = new int[n];for (int i = 0; i < n; i++) weight[i] = sc.nextInt();for (int i = 0; i < n; i++) value[i] = sc.nextInt();for (int i = 0; i < n; i++) nums[i] = sc.nextInt();int[] dp = new int[bagWeight + 1];//先遍历物品再遍历背包，作为01背包处理for (int i = 0; i < n; i++) {for (int j = bagWeight; j >= weight[i]; j--) {//遍历每种物品的个数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(dp[bagWeight]);}
}

分析：时间复杂度：O(mnk)，空间复杂度：O(n)。m：物品种类个数，n背包容量，k单类物品数量。

背包问题总结

文档讲解：https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html