思路：

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]);}
}