背包問題（動歸）

問能否能裝滿背包（或者最多裝多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 對應題目如下：

416.分割等和子集 (物品正序，背包倒序)

問裝滿背包有幾種方法：dp[j] += dp[j - nums[i]] ，對應題目如下：

518. 零錢兌換 II(opens new window)

問背包裝滿最大價值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，對應題目如下：

474.一和零

問裝滿背包所有物品的最小個數：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，對應題目如下：

322.零錢兌換(最少個數) 正序先物品再背包

279.完全平方數(最小數量) 先背包后物品

遍歷順序

01背包

完全背包

背包問題，大家都知道，有N件物品和一個最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。

背包問題有多種背包方式，常見的有：01背包、完全背包、多重背包、分組背包和混合背包等等。

要注意題目描述中商品是不是可以重復放入。

即一個商品如果可以重復多次放入是完全背包，而只能放入一次是01背包，寫法還是不一樣的。

問能否能裝滿背包（或者最多裝多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 對應題目如下：

416.分割等和子集 (物品正序，背包倒序)

給你一個 只包含正整數 的非空數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

這道題目就是一道01背包應用類的題目，需要我們拆解題目，然后套入01背包的場景。

01背包相對于本題，主要要理解，題目中物品是nums[i]，重量是nums[i]，價值也是nums[i]，背包體積是sum/2。

class Solution {public boolean canPartition(int[] nums) {/*** 1. 確定dp數組及下標含義 ：容量為j的背包，所背的物品價值最大可以為dp[j]，背包價值等于總和的一半* 2. 遞推公式 dp[j]=Math.max(dp[j],dp(j-nums[i])+nums[i])* 3. 初始化 dp[0]=0 非零dp[]:0 只包含正整數的非空數組，所以非0下標的元素初始化為0* 4. 遍歷順序 dp[j] 如果使用一維dp數組，物品遍歷的for循環放在外層，遍歷背包的for循環放在內層，且內層for循環倒序遍歷！* 5. 推導結果*/if (nums == null || nums.length == 0) {return false;}int sum = 0;for (int num : nums) {sum += num;}//總和為奇數不能平分if (sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < nums.length; i++) {//物品for (int j = target; j >= nums[i]; j--) {//背包 倒序遍歷dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下，每一次完成for-loop，立即檢查是否dp[target] == targetif (dp[target] == target) {return true;}}return dp[target] == target;}
}

動態規劃：1049.最后一塊石頭的重量 II(opens new window)

問裝滿背包有幾種方法：dp[j] += dp[j - nums[i]] ，對應題目如下：

動態規劃：494.目標和(opens new window)

518. 零錢兌換 II(opens new window)

給你一個整數數組 coins 表示不同面額的硬幣，另給一個整數 amount 表示總金額。

請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。

假設每一種面額的硬幣有無限個。

/*** 先物品后背包的情況下，根據遞推公式，dp【j】一定是來自于外層上一次的結果，而外層上一次的結果一定是來源于上一個物品的dp數組，所以不會出現物品2在物品1之前的情況，也就是只會出現【物品1，物品1，物品2】這種情況，而物品2不會出現在物品1之前，（不會重復）恰好對應組合問題；* 而外層遍歷背包 內層遍歷物品就不一樣了，每一層的dp【j】都是在固定j的情況下，把物品從頭開始遍歷，所以dp【j】來自于上一層的結果，而上一層的結果又遍歷了所有物品，所以這種遍歷方式會出現【物品1，物品2，物品1】這種情況，恰好對應了排列問題* 組合不強調元素之間的順序，排列強調元素之間的順序。* * 1.dp[j]：湊成總金額j的貨幣組合數為dp[j]* 2.dp[j] 就是所有的dp[j - coins[i]]（考慮coins[i]的情況）相加。* dp[j] += dp[j - coins[i]];* 3.初始化  dp[0] = 1 下標非0的dp[j]初始化為0，這樣累計加dp[j - coins[i]]的時候才不會影響真正的dp[j]* 4.遍歷順序 先物品后背包* 如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。* 如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。*/
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0]=1;//判斷條件決定遍歷的背包還是物體  求的是組合數for (int i = 0; i <coins.length; i++) {//物品   for (int j = coins[i]; j <=amount ; j++) {//背包  價值到背包dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}

動態規劃：377.組合總和Ⅳ(opens new window)
動態規劃：70. 爬樓梯進階版（完全背包）(opens new window)

問背包裝滿最大價值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，對應題目如下：

474.一和零

給你一個二進制字符串數組 strs 和兩個整數 m 和 n 。

請你找出并返回 strs 的最大子集的長度，該子集中最多有 m 個 0 和 n 個 1

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

問裝滿背包所有物品的最小個數：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，對應題目如下：

完全背包統一正序遍歷

322.零錢兌換(最少個數) 正序先物品再背包

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。

計算并返回可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

class Solution {/*** 1.確定dp數組以及下標的含義* dp[i]: 湊足總額為j所需錢幣的最少個數為dp[j]* 2.遞推公式 在進行遞推公式之前通常有對應的條件判斷* dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);* 3.初始化* dp[0]=0 dp[j]初始化成比較大的數，防止被覆蓋* 4.遍歷順序 完全背包（個數不受限制）* 完全背包是正序遍歷 求組合數就是外層for循環遍歷物品，內層for遍歷背包。求排列數就是外層for遍歷背包，內層for循環遍歷物品。*/public int coinChange(int[] coins, int amount) {//初始化dp數組為最大值int max = Integer.MAX_VALUE;//錢數需要的最少硬幣int[] dp = new int[amount + 1];Arrays.fill(dp, max);//初始化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]] != max) {//選擇硬幣數目最小的情況dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);}}}//三目運算符比較好用 沒有最小值就返回-1return dp[amount]== max ? -1 : dp[amount];}
}

279.完全平方數(最小數量) 先背包后物品

給你一個整數 n ，返回和為 n 的完全平方數的最少數量。

class Solution {public int numSquares(int n) {/*** 完全平方數就是物品（可以無限件使用），湊個正整數n就是背包，問湊滿這個背包最少有多少物品？* 1.確定dp數組以及下標的含義* dp[i]: 和為 j 的完全平方數的最少數量為dp[j]* 2.遞推公式 在進行遞推公式之前通常有對應的條件判斷* dp[j] = Math.min(dp[j - i*i] + 1, dp[j]);* 3.初始化* dp[0]=0 dp[j]初始化成比較大的數，防止被覆蓋* 4.遍歷順序 完全背包（個數不受限制）* 完全背包是正序遍歷* 求排列數就是外層for遍歷背包，內層for循環遍歷物品。*/// 定義：和為 i 的平方數的最小數量是 dp[i]int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);// base casedp[0] = 0;// 狀態轉移方程for (int i = 1; i <= n; i++) {for (int j = 1; j * j <= i; j++) {// i - j * j 只要再加一個平方數 j * j 即可湊出 idp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}        `                    
}