思路：

1. 確定dp數組含義：dp[i][j] 表示從下標為[0-i]的物品，每個物品可以取無限次，放進容量為j的背包，價值總和最大是多少。
2. 確定遞推公式：（和01背包相似，所以只講區別）
   • 在01背包中，每個物品只有一個，既然空出物品1，那背包中也不會再有物品1。所以空出來之后，去上一層找，即dp[i-1][j-weight[i]]
   • 而在完全背包中，每個物品可以無限取，即使空出物品1空間重量，那背包中也可能還有物品1。所以空出來之后，要從本層取，即dp[i][j-weight[i]]
   • 得出遞推公式：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
3. 初始化：初始化第一行，從背包能放得下weight[0]這個東西開始，往后遍歷。能放多少是多少。
4. 確定遍歷順序，每個dp[i][j]，都要靠左邊，上邊的值確定數據。所以是從上往下，從左往右。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int bagSize = in.nextInt();int[] weight = new int[n];int[] value = new int[n];for (int i = 0; i < n; i++) {weight[i] = in.nextInt();value[i] = in.nextInt();}int[][] dp = new int[n][bagSize + 1];// 初始化第一行，從背包能放得下weight[0]這個東西開始，往后遍歷for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = dp[0][j - weight[0]] + value[0];}// 動態規劃for (int i = 1; i < n; i++) {for (int j = 1; j <= bagSize; j++) {// 當前背包放不下weight[i]，直接等于上一層if (j < weight[i]) {dp[i][j] = dp[i - 1][j];} else {// 這里的遞歸公式，與01背包不同。要空出weight[i]的時候，看的是本層的dp// 區別在于，這里是dp[i][j - weight[i]]，而01背包是：dp[i-1][j - weight[i]]dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);}}}System.out.println(dp[n - 1][bagSize]);}
}

思路：二維dp數組

1. 確定dp[i][j]含義，從0-i的coins中，任選一個或多個，裝滿容量為j的背包（注意是裝滿）
2. 確定遞推公式：
   1. 注意這里求的是“最大組合數”，而不是“最大價值”，所以是加法（情況一+二）
   2. 情況一，不放coins[i]，就是dp[i-1][j]，情況二，放coins[i]，就是dp[i][j-coins[i]]
   3. 注意這里不是[i-1]了，是[i]。不是看上層的，而是看本層的，這是完全背包和01背包的關鍵區別
3. 初始化
   1. 初始化第一列：都有“不選”的選擇，所以是1
   2. 初始化第一行：要能取模的才能賦值1，比如最小貨幣是2的話，當j==3，是不能裝滿的

// 確定dp[i][j]含義，從0-i的coins中，任選一個或多個，裝滿容量為j的背包
class Solution {public int change(int amount, int[] coins) {// amount 是 bagSizeint n = coins.length;int[][] dp = new int[n][amount + 1];// 初始化第一列for (int i = 0; i < n; i++) {// 都有“不選”的選擇，所以是1dp[i][0] = 1;}// 初始化第一行for (int j = coins[0]; j <= amount; j++) {// 特別注意，要能取模的才能賦值1，比如最小貨幣是2的話，當j==3，是不能裝滿的if (j % coins[0] == 0) {dp[0][j] = 1;}}// 動態規劃for (int i = 1; i < n; i++) {for (int j = 1; j <= amount; j++) {// 當前硬幣大于背包容量，直接等于上一層if (j < coins[i]) {dp[i][j] = dp[i - 1][j];} else {// 注意這里求的是“最大組合數”，而不是“最大價值”，所以是加法（情況一+二）// 情況一，不放coins[i]，就是dp[i-1][j]// 情況二，放coins[i]，就是dp[i][j-coins[i]]// 注意這里不是[i-1]了，是[i]。不是看上層的，而是看本層的，這是完全背包和01背包的關鍵區別dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];}}}return dp[n - 1][amount];}
}

思路：一維dp數組

1. dp[i][j]含義不變
2. 遞推公式：
   1. 本題 二維dp 遞推公式： dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]（正上方，左方）
   2. 壓縮成一維：dp[j] = dp[j] + dp[j - coins[i]]
3. 初始化：dp[0] = 1
4. 遍歷順序
   1. 在01背包的時候，遍歷j是要倒序遍歷的，因為dp[j]要依靠“正上方”和“左上方”的數據。但是完全背包，它依賴的是：“正上方”和“左方”的數據。
   2. “左方”的數據由何而來？得先遍歷才有，所以是for(j)是順序遍歷

附：01背包時候的二維公式和一維公式

二維： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - coins[i]]（正上方+左上方）

一維：dp[j] = dp[j] + dp[j - nums[i]];

因為要依賴左上方的數據，也就是上一層的舊數據，所以只能倒序遍歷。遍歷右的時候能取到左的數據

// 確定dp[i][j]含義，從0-i的coins中，任選一個或多個，裝滿容量為j的背包
class Solution {public int change(int amount, int[] coins) {// amount 是 bagSizeint n = coins.length;int[] dp = new int[amount + 1];// 初始化dp[0] = 1;// 動態規劃for (int i = 0; i < n; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] = dp[j] + dp[j - coins[i]];}}return dp[amount];}
}

寫在前面：這個題目很有迷惑性，說是“組合”總和，但是這個“組合”又是可以有不同序列的——其實就是“排列”數，而不是求“組合”數。一定要弄清楚這個再繼續。

思路：一維dp數組

1. dp[j]的定義：從[0-i]（可重復）取任意個數，填滿背包j的組合（可排列！）有多少種？
2. 確定遞歸公式：dp[j] = dp[j] + dp[j - nums[i]];（和上題一樣，不再詳細分析）
3. 初始化：dp[0] = 1;
4. 遍歷順序：先遍歷背包，再遍歷數字！！！先遍歷背包，再遍歷數字！！！先遍歷背包，再遍歷數字！！！

// 一維dp數組
// dp[j]的定義：從[0-i]（可重復）取任意個數，填滿背包j的組合（可排列！）有多少種？
class Solution {public int combinationSum4(int[] nums, int target) {int n = nums.length;// bagSize 是 targetint[] dp = new int[target + 1];// 初始化dp[0] = 1;// 動態規劃for (int j = 0; j <= target; j++) {for (int i = 0; i < n; i++) {if (j >= nums[i]) {dp[j] = dp[j] + dp[j - nums[i]];}}// // 遍歷dp檢查// for(int k=0;k<=target;k++){//     System.out.print(dp[k]+" ");// }// System.out.println(" ");}return dp[target];}
}

《代碼隨想錄》：

這其實是一個完全背包問題。

1階，2階，… m階就是物品，樓頂就是背包。

每一階可以重復使用，例如跳了1階，還可以繼續跳1階。

問跳到樓頂有幾種方法其實就是問裝滿背包有幾種方法。

思路：

1. 確定dp含義：dp[i]：爬到有i個臺階的樓頂，有dp[i]種方法。
2. 確定遞推公式：dp[j] += dp[j - i];
3. 初始化：dp[0] = 1;
4. 完全背包問題：先背包，后數字（因為要先固定背包容量，再取數字，才有不同的順序）

要是能識別出來是完全背包問題，然后又剛好做完上一題的話，這道題其實可以直接復制過去AC。

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();// bagSize 是 n// coins[] 是 m, [1,2,3...m]// dpint[] dp = new int[n + 1];// 初始化dp[0] = 1;// 先背包，后數字for (int j = 0; j <= n; j++) {for (int i = 1; i <= m; i++) {if (j >= i) {dp[j] += dp[j - i];}}}System.out.println(dp[n]);}
}