【動態規劃】深入動態規劃：背包問題

文章目錄

前言
01背包例題
- 一、01背包
- 二、分割等和子集
- 三、目標和
- 四、最后一塊石頭的重量||
完全背包例題
- 一、完全背包
- 二、零錢兌換
- 三、零錢兌換||
- 四、完全平方數

在這里插入圖片描述

前言

什么是背包問題，怎么解決算法中的背包問題呢？

背包問題 (Knapsack problem) 是?種組合優化的 NP完全問題。問題可以描述為：給定?組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。根據物品的個數，分為如下幾類：
? 01 背包問題：每個物品只有?個
? 完全背包問題：每個物品有?限多個
? 多重背包問題：每件物品最多有 si 個
? 混合背包問題：每個物品會有上面三種情況…
? 分組背包問題：物品有 n 組，每組物品里有若干個，每組里最多選一個物品其中上述分類里面，根據背包是否裝滿，又分為兩類：
? 不?定裝滿背包 ? 背包?定裝滿優化方案：
? 空間優化 - 滾動數組
? 單調隊列優化
? 貪心優化根據限定條件的個數，又分為兩類：
? 限定條件只有?個：比如體積 -> 普通的背包問題
? 限定條件有兩個：比如體積 + 重量 -> ?維費用背包問題根據不同的問法，又分為很多類：
? 輸出方案
? 求方案總數
? 最優方案
? 方案可行性
其實還有很多分類，但是我們僅需了解即可。因此，背包問題種類非常繁多，題型非常豐富，難度也是非常難以捉摸。但是，盡管種類非常多，都是從 01 背包問題演化過來的。所以，?定要把 01 背包問題學好。

本文主要介紹兩種背包問題

01背包問題
完全背包問題

下面本文將通過例題為大家詳細展開背包問題，以及背包問題在算法中的具體體現與解法

01背包例題

一、01背包

題目鏈接：01背包
題目描述：

描述
你有?個背包，最多能容納的體積是V。現在有 n 個物品，第 i 個物品的體積為 vi, 價值為 wi。
（1）求這個背包至多能裝多大價值的物品？
（2）若背包恰好裝滿，求?多能裝多大價值的物品？輸入描述：第?行兩個整數 n 和 V，表示物品個數和背包體積。接下來 n 行，每行兩個數 vi 和 wi，表示第i個物品的體積和價值。輸出描述：輸出有兩行，第一行輸出第?問的答案，第?行輸出第?問的答案，如果無解請輸出 0。
示例1 輸入：
3 5
2 10
4 5
1 4
輸出：
14
9
說明：裝第?個和第三個物品時總價值最大，但是裝第?個和第三個物品可以使得背包恰好裝滿且總價值最?。
示例2
輸入：
3 8
12 6
11 8
6 8
輸出：80
說明：裝第三個物品時總價值最?但是不滿，裝滿背包無解

解法：
算法思路：我們先解決第?問：
狀態表示：
dp[i][j] 表?：從前 i 個物品中挑選，總體積「不超過」 j ，所有的選法中，能挑選出來的最大價值。
狀態轉移?程：線性 dp 狀態轉移方程分析?式，?般都是根據「最后?步」的狀況，來分情況討論：
i. 不選第 i 個物品：相當于就是去前 i - 1 個物品中挑選，并且總體積不超過 j 。此時 dp[i][j] = dp[i - 1][j] ；
ii. 選擇第 i 個物品：那么我就只能去前 i - 1 個物品中，挑選總體積不超過 j - v[i]
的物品。此時 dp[i][j] = dp[i - 1][j - v[i]] + w[i] 。但是這種狀態不?
定存在，因此需要特判?下。綜上，狀態轉移?程為： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]]+ w[i]) 。
初始化：我們多加?行，方便我們的初始化，此時僅需將第?行初始化為 0 即可。因為什么也不選，也能滿足體積不小于 j 的情況，此時的價值為 0 。
填表順序：根據「狀態轉移?程」，我們僅需「從上往下」填表即可。
返回值：根據「狀態表?」，返回 dp[n][V] 。接下來解決第?問：第?問僅需微調?下 dp 過程的五步即可。因為有可能湊不齊 j 體積的物品，因此我們把不合法的狀態設置為 -1 。
狀態表示：
dp[i][j] 表示：從前 i 個物品中挑選，總體積「正好」等于 j ，所有的選法中，能挑選出來的最大價值。
狀態轉移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]) 。但是在使用 dp[i - 1][j - v[i]] 的時候，不僅要判斷 j >= v[i] ，又要判斷 dp[i - 1][j - v[i]] 表示的情況是否存在，也就是 dp[i - 1][j - v[i]] != -1 。
初始化：我們多加一行，方便我們的初始化：
i. 第?個格?為 0 ，因為正好能湊?體積為 0 的背包；
ii. 但是第?行后面的格子都是 -1 ，因為沒有物品，無法滿足體積大于 0 的情況。
填表順序：根據「狀態轉移方程」，我們僅需「從上往下」填表即可。
返回值：由于最后可能湊不成體積為 V 的情況，因此返回之前需要「特判」?下
代碼示例

 public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int V = sc.nextInt();//存放體積int[] v=new int[n+1];//存放價值int[] w=new int[n+1];for(int i=1;i<=n;i++){v[i]=sc.nextInt();w[i]=sc.nextInt();}//dp1[i]表示不考慮背包是否裝滿，在容量為i的情況下，最多裝多大價值的物品int[] dp1=new int[V+1];for(int i=1;i<=n;i++){//由于每個物品只能用一次，為了防止重復計算，需要倒序遍歷for(int j=V;j>=v[i];j--){//狀態轉移，要么選擇第i件物品，要么不選，取價值最大的dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j]);}}System.out.println(dp1[V]);//dp2[i]表示背包恰好裝滿時，在容量為i的情況下，最多裝多大價值的物品int[] dp2=new int[V+1];Arrays.fill(dp2,Integer.MIN_VALUE);//沒有物品時，價值為0dp2[0]=0;for(int i=1;i<=n;i++){//由于每個物品只能用一次，為了防止重復計算，需要倒序遍歷for(int j=V;j>=v[i];j--){//狀態轉移，要么選擇第i件物品，要么不選，取價值最大的dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);}}//如果小于0，說明不能從初始狀態轉移過來，無解if(dp2[V]<0){dp2[V]=0;}System.out.println(dp2[V]);}

二、分割等和子集

題目鏈接：分割等和子集
題目描述：

給你?個只包含正整數的 ?空數組 nums 。請你判斷是否可以將這個數組分割成兩個?集，使得兩個?集的元素和相等。 ?例 1：輸?：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。
示例 2：輸?：nums = [1,2,3,5]
輸出：false
解釋：數組不能分割成兩個元素和相等的子集。

解法（動態規劃）：
算法思路：先將問題轉化成我們「熟悉」的題型。如果數組能夠被分成兩個相同元素之和相同的?集，那么原數組必須有下??個性質：
i. 所有元素之和應該是?個偶數；
ii. 數組中最?的元素應該小于所有元素總和的?半；
iii. 挑選?些數，這些數的總和應該等于數組總和的?半。根據前兩個性質，我們可以提前判斷數組能夠被劃分。根據最后?個性質，我們發現問題就轉化成了「01 背包」的模型：
i. 數組中的元素只能選擇?次；
ii. 每個元素?臨被選擇或者不被選擇的處境；
iii. 選出來的元素總和要等于所有元素總和的?半。其中，數組內的元素就是物品，總和就是背包。那么我們就可以?背包模型的分析方式，來處理這道題。請?家注意，「不要背」狀態轉移方程，因為題型變化之后，狀態轉移方程就會跟著變化。我們要記住的是分析問題的模式。?這種分析問題的模式來解決問題。
狀態表示：
dp[i][j] 表示在前 i 個元素中選擇，所有的選法中，能否湊成總和為 j 這個數。
狀態轉移方程： ?規矩，根據「最后?個位置」的元素，結合題?的要求，分情況討論：
i. 不選擇 nums[i] ：那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j 。根據狀態表?，此時 dp[i][j] = dp[i - 1][j] ；
ii. 選擇 nums[i] ：這種情況下是有前提條件的，此時的 nums[i] 應該是?于等于 j 。因為如果這個元素都?要湊成的總和?，選擇它就沒有意義呀。那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j - nums[i] 。根據狀態表 ?，此時 dp[i][j] = dp[i - 1][j - nums[i]] 。
綜上所述，兩種情況下只要有一種能夠湊成總和為 j ，那么這個狀態就是 true 。因此，狀態轉移方程為：dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]]
初始化：由于需要用到上??的數據，因此我們可以先把第?行初始化。第?行表示不選擇任何元素，要湊成目標和 j 。只有當目標和為 0 的時候才能做到，因此第? ?僅需初始化第?個元素 dp[0][0] = true
填表順序：根據「狀態轉移方程」，我們需要「從上往下」填寫每?行，每?行的順序是「無所謂的」。
返回值：根據「狀態表示」，返回 dp[n][aim] 的值。其中 n 表示數組的大小， aim 表示要湊的目標和。
空間優化：所有的「背包問題」，都可以進行空間上的優化。對于 01背包類型的，我們的優化策略是：
i. 刪掉第?維；
ii. 修改第二層循環的遍歷順序即可
代碼示例：

 public boolean canPartition1(int[] nums) {int n = nums.length, sum = 0;for (int x : nums) sum += x;if (sum % 2 == 1) return false; // 如果不能平分，直接返回 falseint aim = sum / 2;boolean[] dp = new boolean[aim + 1]; // 建表dp[0] = true; // 初始化for (int i = 1; i <= n; i++) // 填表for (int j = aim; j >= nums[i - 1]; j--) // ?定要注意修改遍歷順序dp[j] = dp[j] || dp[j - nums[i - 1]];return dp[aim];}

三、目標和

題目鏈接：
題目描述：

給你?個整數數組 nums 和?個整數 target 。向數組中的每個整數前添加 ‘+’ 或 ‘-’ ，然后串聯起所有整數，可以構造?個表達式：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串聯起來得到表達式 “+2-1”
。返回可以通過上述方法構造的、運算結果等于 target 的不同表達式的數目。
示例 1：輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：?共有 5 種方法讓最終目標和為 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：輸?：nums = [1], target = 1 輸出：1

解法（動態規劃）：
算法思路：本題可以直接用「暴搜」的方法解決。但是稍微?數學知識分析?下，就能轉化成我們常見的「背包模型」的問題。設我們最終選取的結果中，前面加 + 號的數字之和為 a ，前?加 - 號的數字之和為 b ，整個數組的總和為 sum ，于是我們有：
? a + b = sum
? a - b = target
上?兩個式子消去 b 之后，可以得到 a = (sum + target) / 2
也就是說，我們僅需在 nums 數組中選擇?些數，將它們湊成和為 (sum + target) / 2 即可。問題就變成了 416. 分割等和?集這道題。我們了可以用相同的分析模式，來處理這道題。
狀態表示：
dp[i][j] 表示：在前 i 個數中選，總和正好等于 j ，?共有多少種選法。
狀態轉移方程：老規矩，根據「最后?個位置」的元素，結合題目的要求，我們有「選擇」最后?個元素或者「不選擇」最后?個元素兩種策略：
i. 不選 nums[i] ：那么我們湊成總和 j 的總方案，就要看在前 i - 1 個元素中選，湊成總和為 j 的?案數。根據狀態表示，此時 dp[i][j] = dp[i - 1][j] ；
ii. 選擇 nums[i] ：這種情況下是有前提條件的，此時的 nums[i] 應該是小于等于 j 。因為如果這個元素都比要湊成的總和?，選擇它就沒有意義呀。那么我們能夠湊成總和為 j 的?案數，就要看在前 i - 1 個元素中選，能否湊成總和為 j - nums[i] 。根據狀態表示，此時 dp[i][j] = dp[i - 1][j - nums[i]]
綜上所述，兩種情況如果存在的話，應該要累加在?起。因此，狀態轉移方程為：dp[i][j] = dp[i - 1][j]
if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i - 1]]
初始化：由于需要用到「上?行」的數據，因此我們可以先把第??初始化。第??表?不選擇任何元素，要湊成?標和 j 。只有當目標和為 0 的時候才能做到，因此第?行僅需初始化第?個元素 dp[0][0] = 1
填表順序：根據「狀態轉移方程」，我們需要「從上往下」填寫每?行，每?行的順序是「無所謂的」。
返回值：根據「狀態表示」，返回 dp[n][aim] 的值。其中 n 表?數組的大小， aim 表示要湊的目標和。
空間優化：所有的「背包問題」，都可以進行空間上的優化。對于 01背包類型的，我們的優化策略是：
i. 刪掉第?維；
ii. 修改第二層循環的遍歷順序即可。
代碼示例：

 public int findTargetSumWays(int[] nums, int target) {int n = nums.length, sum = 0;for (int x : nums) sum += x;int aim = (sum + target) / 2;// 處理?下邊界情況if (aim < 0 || (sum + target) % 2 == 1) return 0;int[] dp = new int[aim + 1];dp[0] = 1;for (int i = 1; i <= n; i++)for (int j = aim; j >= nums[i - 1]; j--) // 注意修改遍歷順序dp[j] += dp[j - nums[i - 1]];return dp[aim];}

四、最后一塊石頭的重量||

題目鏈接：最后一塊石頭的重量||
題目描述：

有?堆石頭，用整數數組 stones 表示。其中 stones[i] 表?第 i 塊?頭的重量。每?回合，從中選出任意兩塊?頭，然后將它們?起粉碎。假設石頭的重量分別為 x 和 y，且 x <=y。那么粉碎的可能結果如下：如果 x == y，那么兩塊石頭都會被完全粉碎；如果 x != y，那么重量為 x 的?頭將會完全粉碎，而重量為 y 的石頭新重量為 y-x。最后，最多只會剩下?塊石頭。返回此石頭最小的可能重量。如果沒有?頭剩下，就返回 0。
示例 1：輸入：stones = [2,7,4,1,8,1]
輸出：1 解釋：組合 2 和 4，得到 2，所以數組轉化為 [2,7,1,8,1]，組合 7 和 8，得到 1，所以數組轉化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數組轉化為 [1,1,1]，組合 1 和 1，得到 0，所以數組轉化為 [1]，這就是最優值。
示例 2：
輸入：stones = [31,26,33,21,40]
輸出：5
提示： 1 <= stones.length <= 30
1 <= stones[i] <= 100

解法（動態規劃）：算法思路：先將問題「轉化」成我們熟悉的題型。
? 任意兩塊?頭在?起粉碎，重量相同的部分會被丟掉，重量有差異的部分會被留下來。那就相當于在原始的數據的前?，加上「加號」或者「減號」，是最終的結果最小即可。也就是說把原始的石頭分成兩部分，兩部分的和越接近越好。
? ?因為當所有元素的和固定時，分成的兩部分越接近數組「總和的?半」，兩者的差越小。因此問題就變成了：在數組中選擇?些數，讓這些數的和盡量接近 sum / 2 ，如果把數看成物品，每個數的值看成體積和價值，問題就變成了「01 背包問題」。
狀態表示：
dp[i][j] 表示在前 i 個元素中選擇，總和不超過 j，此時所有元素的「最?和」。
狀態轉移方程：老規矩，根據「最后?個位置」的元素，結合題目的要求，分情況討論：
i. 不選 stones[i] ：那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j 。根據狀態表?，此時 dp[i][j] = dp[i - 1][j] ；
ii. 選擇 stones[i] ：這種情況下是有前提條件的，此時的 stones[i] 應該是小于等于 j 。因為如果這個元素都比要湊成的總和?，選擇它就沒有意義呀。那么我們是否能夠湊成總和為 j ，就要看在前 i - 1 個元素中選，能否湊成總和為 j - stones[i] 。根據狀態表示，此時 dp[i][j] = dp[i - 1][j - stones[i]] + stones[i] 。
綜上所述，我們要的是最?價值。因此，狀態轉移方程為：dp[i][j] = dp[i - 1][j]
if(j >= stones[i]) dp[i][j] = dp[i][j] + dp[i - 1][j - stones[i]] + stones[i] 。
初始化：由于需要用到上?行的數據，因此我們可以先把第?行初始化。第?行表示「沒有石子」。因此想湊成目標和 j ，最大和都是 0 。
填表順序：根據「狀態轉移方程」，我們需要「從上往下」填寫每?行，每?行的順序是「無所謂的」。
返回值：
a. 根據「狀態表示」，先找到最接近 sum / 2 的最?和 dp[n][sum / 2] ；
b. 因為我們要的是兩堆??的差，因此返回 sum - 2 * dp[n][sum / 2] 。
空間優化：所有的背包問題，都可以進行「空間」上的優化。對于 01背包類型的，我們的優化策略是：
i. 刪掉第?維；
ii. 修改第?層循環的「遍歷順序」即可。
代碼示例：

 public int lastStoneWeightII(int[] stones) {int n = stones.length, sum = 0;for (int x : stones) sum += x;int m = sum / 2;int[] dp = new int[m + 1];for (int i = 1; i <= n; i++)for (int j = m; j >= stones[i - 1]; j--) // 注意修改遍歷順序dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);return sum - 2 * dp[m];}

完全背包例題

一、完全背包

題目鏈接：完全背包
題目描述：

你有?個背包，最多能容納的體積是 V。
現在有 n 種物品，每種物品有任意多個，第i種物品的體積為 vi,價值為 wi。
（1）求這個背包至多能裝多大價值的物品？
（2）若背包恰好裝滿，求至多能裝多大價值的物品？輸?描述：第??兩個整數 n 和 V，表?物品個數和背包體積。接下來 n 行，每行兩個數 vi 和 wi，表?第i種物品的體積和價值。 1 ≤ n,V ≤ 1000
輸出描述：輸出有兩?，第??輸出第?問的答案，第??輸出第?問的答案，如果?解請輸出 0。
示例1 ：
輸入：2 6 5 10
3 1
輸出：10 2
示例2 ：
輸入：
3 8 3 10
9 1
10 1
輸出：20 0
說明：?法恰好裝滿背包。
示例3 輸?：6 13
13 189
17 360
19 870
14 184
6 298
16 242
輸出：596
189
說明：可以裝 5 號物品 2 個，達到最?價值 298*2=596，若要求恰好裝滿，只能裝 1 個 1 號物品，價值為189.

解法（動態規劃）：
算法思路：背包問題的狀態表示非常經典，如果大家不知道怎么來的，就把它當成?個模板記住吧~ 我們先解決第?問：
狀態表示：
dp[i][j] 表示：從前 i 個物品中挑選，總體積不超過 j ，所有的選法中，能挑選出來的最大價值。（這里是和 01背包?樣噠）
狀態轉移方程：線性 dp 狀態轉移方程分析方式，?般都是根據最后一步的狀況，來分情況討論。但是最后一個物品能選很多個，因此我們的需要分很多情況：
i. 選 0 個第 i 個物品：此時相當于就是去前 i - 1 個物品中挑選，總體積不超過 j 。此時最?價值為 dp[i - 1][j] ；
ii. 選 1 個第 i 個物品：此時相當于就是去前 i - 1 個物品中挑選，總體積不超過 j -
v[i] 。因為挑選了?個 i 物品，此時最?價值為 dp[i - 1][j - v[i]] + w[i] ； iii. 選 2 個第 i 個物品：此時相當于就是去前 i - 1 個物品中挑選，總體積不超過 j - 2 * v[i] 。因為挑選了兩個 i 物品，此時最?價值為 dp[i - 1][j - 2 * v[i]] + 2 * w[i] ；
iv. …
綜上，我們的狀態轉移方程為：
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-2v[i]]+2w[i]…)
當我們發現，計算?個狀態的時候，需要?個循環才能搞定的時候，我們要想到去優化。優化的方向就是用?個或者兩個狀態來表?這?堆的狀態，通常就是?數學的?式做?下等價替換。我們發現第?維是有規律的變化的，因此我們去看看 dp[i][j - v[i]] 這個狀態：dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2v[i]]+w[i],dp[i-1][j-3v[i]]+2*w[i]…)
我們發現，把 dp[i][j - v[i]] 加上 w[i] 正好和 dp[i][j] 中除了第?項以外的全部 ?致，因此我們可以修改我們的狀態轉移?程為：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
初始化：我們多加?行，方便我們的初始化，此時僅需將第?行初始化為 0 即可。因為什么也不選，也能滿?體積不?于 j 的情況，此時的價值為 0 。
填表順序：根據狀態轉移?程，我們僅需從上往下填表即可。
返回值：根據狀態表示，返回 dp[n][V] 。
接下來解決第?問：第?問僅需微調?下 dp 過程的五步即可。因為有可能湊不齊 j 體積的物品，因此我們把不合法的狀態設置為 -1 。
狀態表示：
dp[i][j] 表示：從前 i 個物品中挑選，總體積正好等于 j ，所有的選法中，能挑選出來的最大價值。
狀態轉移方程：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。但是在使用 dp[i][j - v[i]] 的時候，不僅要判斷 j >= v[i] ，又要判斷 dp[i][j - v[i]] 表示的情況是否存在，也就是 dp[i][j - v[i]] != -1 。
初始化：我們多加?行，方便我們的初始化：
i. 第?個格子為 0 ，因為正好能湊齊體積為 0 的背包；
ii. 但是第?行后面的格子都是 -1 ，因為沒有物品，無法滿足體積大于 0 的情況。
填表順序：根據狀態轉移方程，我們僅需從上往下填表即可。
返回值：由于最后可能湊不成體積為 V 的情況，因此返回之前需要特判?下
代碼示例：

import java.util.Scanner;public class KnapsackProblem {// 定義常量static final int N = 1010;static int n, V;static int[] v = new int[N];static int[] w = new int[N];static int[] dp = new int[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀入數據n = scanner.nextInt();V = scanner.nextInt();for (int i = 1; i <= n; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}// 搞定第一問for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}System.out.println(dp[V]);// 第二問for (int j = 1; j <= V; j++) {dp[j] = Integer.MIN_VALUE;}for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= V; j++) {dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}System.out.println(dp[V] < 0? 0 : dp[V]);scanner.close();}
}

二、零錢兌換

題目鏈接：零錢兌換
題目描述：

給你?個整數數組 coins ，表示不同面額的硬幣；以及?個整數 amount ，表示總金額。計算并返回可以湊成總金額所需的最少的硬幣個數。如果沒有任何?種硬幣組合能組成總金額，返回 -1 。你可以認為每種硬幣的數量是無限的。
示例 1：輸?：coins = [1, 2, 5], amount = 11
輸出：3 解釋：11 = 5 + 5 + 1
示例 2：輸?：coins = [2], amount = 3 輸出：-1
?例 3：輸?：coins = [1], amount = 0 輸出：0
提示：1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1 0 <= amount <= 104

解法（動態規劃）：算法思路：先將問題「轉化」成我們熟悉的題型。
i. 在?些物品中「挑選」?些出來，然后在滿足某個「限定條件」下，解決?些問題，大概率是「背包」模型；
ii. 由于每?個物品都是無限多個的，因此是?個「完全背包」問題。接下來的分析就是基于「完全背包」的?式來的。
狀態表示：
dp[i][j] 表示：從前 i 個硬幣中挑選，總和正好等于 j ，所有的選法中，最少的硬幣個數。
狀態轉移?程：線性 dp 狀態轉移方程分析方式，?般都是根據「最后?步」的狀況，來分情況討論。但是最后一個物品能選很多個，因此我們的需要分很多情況：
i. 選 0 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j 。此時最少的硬幣個數為 dp[i - 1][j] ；
ii. 選 1 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j - v[i] 。因為挑選了?個 i 硬幣，此時最少的硬幣個數為 dp[i - 1][j - coins[i]] + 1 ；
iii. 選 2 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j - 2 * coins 。因為挑選了兩個 i 硬幣，此時最少的硬幣個數為 dp[i - 1][j - 2 * coins[i]] + 2 ；
iv. …
結合我們在完全背包里面的優化思路，我們最終得到的狀態轉移方程為：
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1) 。這里教給大家?個技巧，就是相當于把第?種情況 dp[i - 1][j - coins[i]] + 1 ? ?的 i - 1 變成 i 即可。
初始化：初始化第?行即可。這?因為取 min ，所以我們可以把無效的地方設置成無窮大 (0x3f3f3f3f)
因為這?要求正好湊成總和為 j ，因此，需要把第?行除了第?個位置的元素，都設置成無窮大。
填表順序：根據「狀態轉移方程」，我們僅需「從上往下」填表即可。
返回值：根據「狀態表?」，返回 dp[n][V] 。但是要特判?下，因為有可能湊不到。
代碼示例：

public int coinChange(int[] coins, int amount) {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int n = coins.length, INF = 0x3f3f3f3f;int[] dp = new int[amount + 1];for (int j = 1; j <= amount; j++) dp[j] = INF;for (int i = 1; i <= n; i++)for (int j = coins[i - 1]; j <= amount; j++)dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);return dp[amount] >= INF ? -1 : dp[amount];}

三、零錢兌換||

題目鏈接：零錢兌換||
題目描述：

給你?個整數數組 coins 表?不同?額的硬幣，另給?個整數 amount 表示總金額。請你計算并返回可以湊成總?額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回 0 。假設每?種?額的硬幣有?限個。題目數據保證結果符合 32 位帶符號整數。
示例 1：輸入：amount = 5, coins = [1, 2, 5]
輸出：4 解釋：有四種方式可以湊成總?額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
輸入：amount = 3, coins = [2]
輸出：0 解釋：只用面額 2 的硬幣不能湊成總?額 3 。
示例 3：
輸入：amount = 10, coins = [10]
輸出：1
提示：1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值互不相同 0 <= amount <= 5000

解法（動態規劃）：
算法思路：先將問題「轉化」成我們熟悉的題型。
i. 在?些物品中「挑選」?些出來，然后在滿?某個「限定條件」下，解決?些問題，?概率是背包模型；
ii. 由于每?個物品都是無限多個的，因此是?個「完全背包」問題。接下來的分析就是基于「完全背包」的?式來的。
狀態表示：
dp[i][j] 表?：從前 i 個硬幣中挑選，總和正好等于 j ，?共有多少種選法。
狀態轉移?程：線性 dp 狀態轉移方程分析方式，?般都是「根據最后?步」的狀況，來分情況討論。但是最后 ?個物品能選很多個，因此我們的需要分很多情況：
i. 選 0 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j 。此時最少的硬幣個數為 dp[i - 1][j] ；
ii. 選 1 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j - v[i] 。因為挑選了?個 i 硬幣，此時最少的硬幣個數為 dp[i - 1][j - coins[i]] + 1 ；
iii. 選 2 個第 i 個硬幣：此時相當于就是去前 i - 1 個硬幣中挑選，總和正好等于 j - 2 * coins 。因為挑選了兩個 i 硬幣，此時最少的硬幣個數為 dp[i - 1][j - 2 * coins[i]] + 2 ；
iv. …
結合我們在完全背包里面的「優化思路」，我們最終得到的狀態轉移?程為：
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]] + 1 。這里教給?家?個技巧，就是相當于把第?種情況 dp[i - 1][j - coins[i]] + 1 里面的 i - 1 變成 i 即可。
初始化：初始化第?行即可。第?行表示沒有物品，沒有物品正好能湊能和為 0 的情況。因此 dp[0][0] = 1 ，其余位置都是 0 種情況。
填表順序：根據「狀態轉移方程」，我們僅需「從上往下」填表即可。
返回值：根據「狀態表示」，返回 dp[n][V] 。
代碼示例：

 public int change(int amount, int[] coins) {// 空間優化int[] dp = new int[amount + 1]; // 建表dp[0] = 1; // 初始化for (int x : coins) // 拿出物品for (int j = x; j <= amount; j++) // 注意遍歷順序和起始終?位置dp[j] += dp[j - x];return dp[amount];}

四、完全平方數

題目鏈接：完全平方數
題目描述：

給你?個整數 n ，返回和為 n 的完全平方數的最少數量。完全平方數是?個整數，其值等于另一個整數的平方；換句話說，其值等于?個整數自乘的積。例如，1、4、9 和 16 都是完全平方數，而 3 和 11 不是。
示例 1：輸入：n = 12
輸出：3
解釋：12 = 4 + 4 + 4
示例 2：輸入：n = 13
輸出：2
解釋：13 = 4 + 9

解法（動態規劃）：算法思路：
這里給出?個用「拆分出相同?問題」的?式，定義?個狀態表?。（用「完全背包」?式的解法就仿照之前的分析模式就好啦~~）
為了敘述方便，把和為 n 的完全平方數的最少數量簡稱為「最?數量」。
對于 12 這個數，我們分析?下如何求它的最?數量。
? 如果 12 本身就是完全平?數，我們不?算了，直接返回 1 ；
? 但是 12 不是完全平?數，我們試著把問題分解?下：
情況?：拆出來?個 1 ，然后看看 11 的最小數量，記為 x1 ；
情況?：拆出來?個 4 ，然后看看 8 的最小數量，記為 x2 ；（為什么拆出來 4 ，而不拆出來 2 呢？）
情況三：拆出來?個 8 …
其中，我們接下來求 11、8 的時候，其實又回到了原來的問題上。因此，我們可以嘗試用 dp 的策略，將 1 2 3 4 6 等等這些數的最小數量依次保存起來。再求較大的 n 的時候，直接查表，然后找出最?數量。
狀態表示：
dp[i] 表示：和為 i 的完全平方數的最少數量。
狀態轉移?程：對于 dp[i] ，根據思路那?的分析我們知道，可以根據?于等于 i 的所有完全平方數 x 進行劃分：
? x = 1 時，最?數量為： 1 + dp[i - 1] ；
? x = 4 時，最?數量為： 1 + dp[i - 4] …
?直枚舉到 x <= i 為?。
為了方便枚舉完全平方數，我們采用下面的策略： for(int j = 1; j * j <= i; j++)
綜上所述，狀態轉移方程為：dp[i] = min(dp[i], dp[i - j * j] + 1)
初始化：當 n = 0 的時候，沒法拆分，結果為 0 ；當 n = 1 的時候，顯然為 1 。
填表順序：從左往右。
返回值：根據題意，返回 dp[n] 的值。
代碼示例：

public int numSquares(int n) {int[] dp = new int[n + 1];dp[1] = 1; // 初始化for (int i = 2; i <= n; i++) // 枚舉每個數{dp[i] = 1 + dp[i - 1]; // ?少等于 1 + dp[i - 1]for (int j = 2; j * j <= i; j++) // ??于 i 的完全平?數劃分區間dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 拿到所有劃分區間內 的最?值}// 返回結果return dp[n];}