Day38--动态规划--322. 零钱兑换，279. 完全平方数，139. 单词拆分，56. 携带矿石资源（卡码网），背包问题总结

思路：

1. 确定dp含义：dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

2. 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]

   然后dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

   递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3. dp[0] = 0;

4. 遍历顺序：都可以，因为求的不是排列数或者组合数。

class Solution {public int coinChange(int[] coins, int amount) {// 最大值，因为要用到Math.minint max = Integer.MAX_VALUE;int n = coins.length;// bagSize 是 amountint[] dp = new int[amount + 1];// 初始化Arrays.fill(dp, max);dp[0] = 0;// 动态规划for (int i = 0; i < n; i++) {// 多重背包，要正序for (int j = coins[i]; j <= amount; j++) {// 不等于max，才证明是由硬币组成的if (dp[j - coins[i]] != max) {// 等式左边的dp[j]，是更新后的，是这一层的// 等式右边的dp[j]，是更新前的，是上一层的// 等式右边的dp[j - coins[i]]，在dp[j]的左边，所以是同一层的，已经更新过的// 对于`dp[j - coins[i]] + 1`这个因素，它的意思是，腾出coins[i]的空间之后，在本层找[j - coins[i]]这个位置是需要多少硬币的，+1（加上当前遍历的这枚coins[i]）就是当前位置的硬币数了dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}// // 打印观察// for (int k = 0; k <= amount; k++) {//     System.out.print(dp[k]+" ");// }// System.out.println(" ");}return dp[amount] == max ? -1 : dp[amount];}
}

简洁版：

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int n = coins.length;int[] dp = new int[amount + 1];Arrays.fill(dp, max);dp[0] = 0;for (int i = 0; i < n; i++) {for (int j = coins[i]; j <= amount; j++) {if (dp[j - coins[i]] != max) {dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];}
}

思路：

1. 确定dp数组含义：dp[j]就是和为 j 的完全平方数的最少数量 。
2. 递推公式：dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
   • 情况一：就是等于上一层。
   • 情况二如果要等于这一层的话，先取：减去当前的数字i的平方那个位置的数量，然后加i这“一位”数，所以+1
   • 然后情况一、二取最小值。
3. 初始化：
   • dp[0] 是无意义的，因为没有数的平方等于0。但是初始化需要dp[0] = 0;
   • 因为有了Math.min()，所以非0下标的地方要全部赋值max
4. 遍历顺序：只要数量，那就求排列数或者组合数都可以。那就是先背包再数字，或者先数字再背包都可以。
5. 额外的剪枝优化：可以减少遍历数量。要平方得到n，最少只需要一个根号n，所以遍历到的最大值设为√n就好。

// bagSize 是 n
// nums[] 的上限是 Math.sqrt(n);
class Solution {public int numSquares(int n) {// 需要用到Math.minint max = Integer.MAX_VALUE;// 剪枝，可以减少遍历数量。要平方得到n，最少只需要一个根号nint numsMax = (int) Math.sqrt(n);// 一维dp数组int[] dp = new int[n + 1];// 初始化Arrays.fill(dp, max);// dp[0] 是无意义的，因为没有数的平方等于0。但是初始化需要，不然是max的话，做不了了dp[0] = 0;// i从1开始for (int i = 1; i <= numsMax; i++) {// j直接从i方开始遍历,因为小于i方的数,本层都更新不了,等于上层数据for (int j = i * i; j <= n; j++) {// 肯定要min的，比如n=16，直接是1个4方就够了，而不是4个2方// 为什么是+1？遍历到了数值i了，这一层先腾空i*i的空间，再往前找dp[j - i * i]的数量，加上i这个数（这一个数），所以就是加1dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}return dp[n];}
}

思路：

1. dp数组含义：字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
2. 递推公式：
   • 如果这个区间是存在于字典里的一个串，这个串的开头，跟已经判断过的内容的结尾是相接的。那么这个串的末尾+1的位置给它赋值为true。
   • 如果确定dp[j] 是true（到j这里都是true），且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
   • 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3. 初始化：dp[0] = true;
4. 遍历顺序：因为字典中的单词，可能会被重复取，所以要按照排列数的方法来做——即先遍历背包，再遍历物品。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordSet = 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; j++) { // 遍历物品String word = s.substring(j, i); //substring(起始位置，结束位置)if (wordSet.contains(word) && dp[j]) {dp[i] = true;}}}return dp[s.length()];}
}

思路：

上面的思路，是不断截取子字符串，判断是否在字典中。

还可以这样做，i往前走，遍历字典里面的所有单词，判断[i - len, i)这个区间的字符串是否跟字典里某个单词相等，是的话，当前位置设为true。（注意substring方法是左闭右开，当前i的位置已经是下一个单词的开头了。所以刚好在索引s.length()的时候，可以返回最终结果）

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for (int i = 1; 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()];}
}

记录：这道题感觉跟常规的背包问题，忽然间不太熟悉，想了许久没出来，直接看题解，理解题目，下次二刷。

这道题目是用来理解多重背包问题的。

多重背包的样子：

实际上，换个角度就变成01背包了：

思路：

所以就是多套一层循环，把物品i遍历对应的次数就行了。按照常规01背包的步骤来做。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 背包容量int bagSize = in.nextInt();// 一共有n种矿石int n = in.nextInt();// 每种矿石的重量int[] weight = new int[n];// 每种矿石的价值int[] value = new int[n];// 每种矿石分别有多少块int[] perAmount = new int[n];// 输入for (int i = 0; i < n; i++) {weight[i] = in.nextInt();}for (int i = 0; i < n; i++) {value[i] = in.nextInt();}for (int i = 0; i < n; i++) {perAmount[i] = in.nextInt();}// dp数组的含义：在bagSize的容量下，最大能取到的总价值int[] dp = new int[bagSize + 1];//动态规划// 遍历每种矿石for (int i = 0; i < n; i++) {// 遍历每种矿石的数量for (int per = 0; per < perAmount[i]; per++) {// 遍历背包容量for (int j = bagSize; j >= weight[i]; j--) {// 常规的01背包的递推公式dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}}// 输出结果System.out.println(dp[bagSize]);}
}