【Java】HOT100+代碼隨想錄 動態規劃（上）背包問題

目錄

理論基礎

?一、基礎題目

LeetCode509：斐波那契數

LeetCode70：爬樓梯

LeetCode746：使用最小花費爬樓梯

LeetCode62：不同路徑

?LeetCode63：不同路徑ii

?LeetCode343：整數拆分

?LeetCode96：不同的二叉搜索樹

二、背包問題

2.1 01背包

01背包理論基礎1：二維dp數組

01背包理論基礎2：滾動/一維dp數組

LeetCode416：分割等和子集（求是否能正好裝滿）

LeetCode1049：最后一塊石頭的重量ii（最多裝多少）

?LeetCode493：目標和（求裝滿背包有多少種方法）

LeetCode474：一和零（求裝滿背包最多有多少個物品）

2.2 完全背包

理論基礎

LeetCode518：零錢兌換ii（求組合數）

?LeetCode377：組合總和iv（求排列）

?LeetCode70：爬樓梯（求排列數）

LeetCode322：零錢兌換（求最小數）

LeetCode279：完全平方數（求最小數）

LeetCode139：單詞拆分

2.3 多重背包

理論基礎

理論基礎

動態規劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態規劃是最有效的。

所以動態規劃中每一個狀態一定是由上一個狀態推導出來的；

舉例：

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

動態規劃中dp[j]是由dp[j-weight[i]]推導出來的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

這一點就區分于貪心，貪心沒有狀態推導，而是從局部直接選最優的。

  • 狀態轉移公式（遞推公式）在動態規劃中相當重要
  • 動態規劃五部曲如下：
  1. 確定dp數組（dp table）以及下標的含義
  2. 確定遞推公式
  3. dp數組如何初始化（很多時候遞推公式決定了dp數組要如何初始化）
  4. 確定遍歷順序
  5. 舉例推導dp數組

在debug時把dp數組打印出來，看看究竟是不是按照自己思路推導的

?一、基礎題目

LeetCode509：斐波那契數

思路：每一個數字等于前兩項之和，給定n求F(n)。動規五部曲——

①dp數組和下標的含義：dp[i]即第i個數的斐波那契數

②遞歸公式：題干中就給出了，dp[i] = dp[i - 1] + dp[i - 2];

③初始化：題干中也給出了，dp[0] = 0，dp[1] = 1；

④遍歷順序：從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的

⑤舉例推導：按照遞推公式，n為10時，dp數組應該是如下的：

0 1 1 2 3 5 8 13 21 34 55（如果結果不對，就打印dp數組）

class Solution {public int fib(int n) {if(n<=1)    return n;int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;for(int i = 2; i<=n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

LeetCode70：爬樓梯

思路：每次你可以爬 1 或 2 個臺階

①dp數組和下標的含義：爬到第i階，有dp[i]種方法

②遞歸公式：爬到i-1階有dp[i-1]種方法，然后再爬一階就是dp[i]；同理，爬到i-2階有dp[i-2]種方法，然后再爬兩階就是dp[i]。所以dp[i] = dp[i - 1] + dp[i - 2]；

③初始化：可以推測出，dp[0] = 0（不重要），dp[1] = 1，dp[2] = 2；

④遍歷順序：從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出遍歷的順序一定是從前到后遍歷的

⑤舉例推導：按照遞推公式，n為5時，dp數組應該是如下的：

0 1 2 3 5 8

發現不就是斐波那契數嗎？！同樣的代碼一點毛病沒有

public int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

也可以使用變量優化一下空間復雜度

class Solution {public int climbStairs(int n) {if(n <= 2) return n;int a = 1, b = 2, sum = 0;for(int i = 3; i <= n; i++){sum = a + b;  // f(i - 1) + f(i - 2)a = b;        // 記錄f(i - 1)，即下一輪的f(i - 2)b = sum;      // 記錄f(i)，即下一輪的f(i - 1)}return b;}
}

LeetCode746：使用最小花費爬樓梯

思路：可以選擇從下標0或者1開始爬，爬1-2階

①dp數組和下標的含義：爬到第i階，所花費的最少體力是dp[i]

②遞歸公式：要算得dp[i]有兩種方法，一個是從dp[i-1]花cost[i-1]向上爬一階，一個是行dp[i-2]花cost[i-2]向上爬兩階，最終使用哪種是最少話費呢？

那就是dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

③初始化：可以推測出，dp[0] = 0，dp[1] = 0；

④遍歷順序：從遞歸公式中可以看出遍歷的順序一定是從前到后遍歷的

⑤舉例推導

class Solution {public int minCostClimbingStairs(int[] cost) {int len = cost.length;int[] dp = new int[len + 1];// 從下標為 0 或下標為 1 的臺階開始，因此支付費用為0dp[0] = 0;dp[1] = 0;// 計算到達每一層臺階的最小費用for (int i = 2; i <= len; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[len];}
}

LeetCode62：不同路徑

思路：如果采用深度搜索，則這棵樹的深度為m+n-1，而深搜代碼的時間復雜度為O(2^(m + n - 1) - 1)，這是非常大的。那么采用動態規劃，從（0,0）出發，到（m，n）：

①dp數組和下標的含義：dp[i][j]表示從（0,0）出發，到達（i,j）有多少種路徑；

②遞歸公式：要算得dp[i][j]有兩種方法，一個是從dp[i-1][j] 向下移動一格，一個是從dp[i][j-1]向右移動一格。dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

③初始化：首先dp[i][0]一定都是1，因為從(0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

④遍歷順序：從遞歸公式中可以看出遍歷的順序是從左到右一層一層遍歷的

⑤舉例推導

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i=0;i<m;i++){dp[i][0] = 1;}for(int i=0;i<n;i++){dp[0][i] = 1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

?LeetCode63：不同路徑ii

思路：相比1，給出了障礙物，路徑需要繞開障礙物。與1的區別僅僅在于：

1. 初始化時如果障礙在邊上，則僅初始化障礙前的dp值為1，障礙后仍為0（無法到達）

2. 在遍歷時跳過給有障礙的dp賦值

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];for(int i=0;i<m && obstacleGrid[i][0] == 0;i++){dp[i][0] = 1;}for(int i=0;i<n && obstacleGrid[0][i] == 0;i++){dp[0][i] = 1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j] == 1)   continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

?LeetCode343：整數拆分

思路：給定一個正整數?n，將其拆分為至少兩個正整數的和，并使這些整數的乘積最大化。?

①dp數組和下標的含義：分拆數字i，所得到的最大乘積是dp[i]

②遞歸公式：要算得dp[i]有兩種方法，從1遍歷j，一個是j*(i-j)，一個是j*dp[i-j]。可以這么理解，j * (i - j) 是單純的把整數拆分為兩個數相乘，而j * dp[i - j]是拆分成兩個以及兩個以上的個數相乘。

那就是dp[i] =?max({dp[i], (i - j) * j, dp[i - j] * j});

在取最大值的時候，為什么還要比較dp[i]呢？因為在遞推公式推導的過程中，每次計算dp[i]，取最大的而已。

③初始化：可以推測出，dp[2] = 1，dp[3] = 2；（n從3開始拆）

④遍歷順序：從遞歸公式中可以看出遍歷的順序一定是從前到后遍歷的，且先有dp[i - j]再有dp[i]。i從3-n，j從1到i-1（不包括i-1），更優化的遍歷方法是：j直接從1到i/2，這是因為一定是拆分成m個近似相同的子數相乘才是最大的

⑤舉例推導

class Solution {public int integerBreak(int n) {int[] dp = new int[n+1];dp[2] = 1;for(int i = 3;i<=n;i++){for(int j = 1;j<=i/2;j++){dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
}

?LeetCode96：不同的二叉搜索樹

思路：重點是推導公式，容易看出

dp[3]，就是 元素1為頭結點搜索樹的數量 + 元素2為頭結點搜索樹的數量 + 元素3為頭結點搜索樹的數量，

元素1為頭結點搜索樹的數量 = 右子樹有2個元素的搜索樹數量 * 左子樹有0個元素的搜索樹數量

元素2為頭結點搜索樹的數量 = 右子樹有1個元素的搜索樹數量 * 左子樹有1個元素的搜索樹數量

元素3為頭結點搜索樹的數量 = 右子樹有0個元素的搜索樹數量 * 左子樹有2個元素的搜索樹數量

即dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

① dp的概念：dp[i]就是以1到i為節點構成的二叉搜索樹的個數

②遞歸公式：i從2開始遍歷到n，j從1開始遍歷到i，dp[i] += dp[j-1]*dp[i-j];

③初始化：dp[0]=1; dp[1] = 1;

④遍歷順序和舉例推導

class Solution {public int numTrees(int n) {//初始化 dp 數組int[] dp = new int[n + 1];//初始化0個節點和1個節點的情況dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {//對于第i個節點，需要考慮1作為根節點直到i作為根節點的情況，所以需要累加//一共i個節點，對于根節點j時,左子樹的節點個數為j-1，右子樹的節點個數為i-jdp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
}

二、背包問題

2.1 01背包

01背包理論基礎1：二維dp數組

（物品下標-背包容量）

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

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

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

二維數組 01背包：

  1. dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。
  2. 遞歸公式：①不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。（其實就是當物品i的重量大于背包j的重量時，物品i無法放進背包中，所以背包內的價值依然和前面相同）。②放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值。
  3. ?dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);?
  4. 初始化：關于初始化，一定要和dp數組的定義吻合，否則到遞推公式的時候就會越來越亂。根據遞推公式可以看出需要得知dp[i][0]和dp[0][j]的初始值，才能開始遞推。可以一開始就統一把dp數組統一初始為0。當背包容量為0時，無論怎么選取物品，都無法放入背包中，即價值為0，dp[i][0] = 0；當放入序號為0的物品時且背包容量為0-j時，所能放下物品的最大價值：當j<weight[0]時，背包里放不下物品0，dp[0][j]應該是0；當j>=weight[0]時，背包里可以放下編號0物品，dp[0][j]應該是value[0]。
  5. 遍歷順序：問題來了，先遍歷物品還是先遍歷背包重量呢？其實都可以！！ 但是先遍歷物品更好理解。
  6. 舉例推導：自己推導一下

例題：卡碼網46 攜帶研究材料（給定背包容量，求裝滿的最大價值）

public class Main {public static void main(String[] args) {int[] weight = {2,2,3,1,5,2};int[] value = {2,3,1,5,4,3};int bagSize = 1;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 創建dp數組int goods = weight.length;  // 獲取物品的數量int[][] dp = new int[goods][bagSize + 1];// 初始化dp數組// 創建數組后，其中默認的值就是0for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}// 填充dp數組for (int i = 1; i < weight.length; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) {/*** 當前背包的容量都沒有當前物品i大的時候，是不放物品i的* 那么前i-1個物品能放下的最大價值就是當前情況的最大價值*/dp[i][j] = dp[i-1][j];} else {/*** 當前背包的容量可以放下物品i* 那么此時分兩種情況：*    1、不放物品i*    2、放物品i* 比較這兩種情況下，哪種背包中物品的最大價值最大*/dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);}}}System.out.println(dp[goods-1][bagSize]);}
}

01背包理論基礎2：滾動/一維dp數組

對于背包問題其實狀態都是可以壓縮的。

在使用二維數組的時候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其實可以發現如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：

dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

即重復利用上一層，與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數組了，只用dp[j]（一維數組，也可以理解是一個滾動數組）。

  1. 在一維數組中，dp[j]代表：容量為j的背包，所背的物品價值可以最大為dp[j]；
  2. 遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；仍然相當于其中一層的不放物品i和放物品i
  3. 初始化：看一下遞推公式，可知只需初始化dp[0]]=0即可；
  4. 遍歷順序：重點是倒序遍歷，是為了確保物品i只被放入一次。二維的就不用倒序，因為二維dp[i][j]計算是通過上一層dp[i - 1][j]得來的，不會覆蓋，而由于一維數組用的是同一個dp[j]，所以會從前向后覆蓋，影響dp值的計算，所以為了避免重復需要倒序。
for(int i = 0; i < weight.size(); i++) { // 遍歷物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

public class Main {public static void main(String[] args) {int[] weight = {2,2,3,1,5,2};int[] value = {2,3,1,5,4,3};int bagSize = 1;testWeightBagProblem(weight,value,bagSize);}public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 創建dp數組int goods = weight.length;  // 獲取物品的數量int[] dp = new int[bagSize + 1];// 初始化dp數組,直接默認全為0// 填充dp數組，放不下的即j < weight[i]就默認不改變，一維數組直接繼承上一層無需賦值，簡化了代碼for (int i = 0; i < goods; i++) {for (int j = bagSize; j >= weight[i]; j--) {dp[j] = Math.max(dp[j] , dp[j-weight[i]] + value[i]);}}System.out.println(dp[bagSize]);}
}

總結：?

1. 為什么二維背包兩個for循環的嵌套順序這么寫？反過來寫行不行？再講一講初始化的邏輯。

答：兩個for循環的順序無非是先遍歷物品還是先遍歷背包容量，在二維數組中其實都行得通，但是遍歷物品更好理解。根據遞推公式，每一個dp[i][j]其實都是由上一個dp[i-1][j]或者上一個dp[i - 1][j - weight[i]] 推導出來的，如果以表格的形式來看，位于dp[i][j]的左上角，如果先遍歷物品，就是在每一個物品都遍歷一遍不同的背包重量，從左到右，從上到下；而如果先遍歷背包容量就是先從上到下，在從左到右，由于數據位于左上角，所以兩個for的順序都不影響dp[i][j]的推導。而這種推導方式顯然要得到所有的dp[0][j]和dp[i][0]公式才能接著往下，往右推導。

2. 改成一維以后，兩個for循環的順序反過來寫行不行？為什么？

答：不可以，改成一維之后只能先遍歷物品再遍歷背包容量，這是由于一維dp的寫法中背包容量一定是要倒序遍歷，其本質上還是對二維數組的遍歷，右下角的值依賴上一層左上角的值，因此需要保證左邊的值仍然是上一層的，從右向左覆蓋，保證每個物品只添加一次。如果非要換順序，倒序遍歷的作用便失去了。

LeetCode416：分割等和子集（求是否能正好裝滿）

思路：是否可以將數組分割成兩個子集，使得子集和相等。

怎么轉換成背包問題呢？

首先，每個元素我們只用一次，所以是01背包問題。背包的最大容量是target = sum/2，放入n個元素，每個元素的值既是他的value，也是他的weight；dp[j]的定義是容量為j的背包里能裝的最大重量，如果正好裝滿，即dp[j] = j。

其次，01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);對于本題，相當于背包里放入數值，那么物品i的重量是nums[i]，其價值也是nums[i]。所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])；01背包的初始化：dp[0] = 0即可。

首先得到背包，最終做判斷如果dp[target] = target，就說明可以分割等和子集。

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int i= 0;i<nums.length;i++){sum += nums[i];}if(sum % 2 == 1)    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]);}}if(dp[target] == target){return true;}return false;}
}

LeetCode1049：最后一塊石頭的重量ii（最多裝多少）

思路：其實本質上就是盡量讓石頭分成重量相同的兩堆，相撞之后剩下的石頭最小，這樣就化解成01背包問題了，同樣是每個物品重量和價值都為stones[i]。target = sum/2。

得到背包后，不用完全相等，一堆石頭是dp[target]，另一堆是sum - dp[target]。由于target = sum/2是向下取整，所以sum - dp[target] >?dp[target]，

所以最終的最小石頭重量為?(sum - dp[target]) - dp[target]。

class Solution {public int lastStoneWeightII(int[] nums) {int sum = 0;for(int i= 0;i<nums.length;i++){sum += nums[i];}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]);}}return sum - 2*dp[target];}
}

?LeetCode493：目標和（求裝滿背包有多少種方法）

思路：如何轉化成01背包問題——

一部分left為+，一部分right為-，left-right = target，left+rght = sum，已知sum和target，就可以求出?left = (target + sum)/2 ，此時問題就變成了在集合中找bagSize = left的組合。

之前的幾道題都是求容量為j的背包，最多能裝多少，本題則是說裝滿有幾種方法，是組合問題。

* 首先排除兩種情況，即①target的絕對值>sum，以及②(target+sum)除以2的余數不為0

1. dp[j]：容量為j的背包能有dp[j]種方法，

2. 遞推公式：求方法的總和——dp[j] += dp[j - nums[i]]

3. 初始化：dp[0] = 1，別的初始化為0；背包容量為0的話，[0]可以有一種取法，[0,0,0,0,0]有32種取法，也是dp[0] = 1疊加起來的

4. 遍歷順序就是01背包的先遍歷物品，再倒序遍歷背包容量

5. 舉例推導：

這道題也可以用回溯來做，甚至可以列出所有組合，dp僅僅可以求個數

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum =0;for(int i=0;i<nums.length;i++){sum += nums[i];}if(Math.abs(target) > sum)  return 0;if((target+sum)%2 == 1) return 0;int bagSize = (target+sum)/2;int[] dp = new int[bagSize+1];dp[0] = 1;for(int i=0;i<nums.length;i++){for(int j=bagSize;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[bagSize];}
}

LeetCode474：一和零（求裝滿背包最多有多少個物品）

思路：strs數組里的元素就相當于是物品，包含zeroNum個0，oneNum個1，這就是一個典型的01背包！?只不過物品的重量有了兩個維度而已。

dp[i][j]就相當于最多有i個0和j個1的最大子集大小，遞推通過加一來實現即可。字符串的zeroNum和oneNum相當于物品的重量（weight[i]），字符串本身的個數相當于物品的價值（value[i]）。

相當于還是先遍歷物品，在內循環里通過構建zeroNum和oneNum兩個雙循環來遍歷背包容量。

01背包遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

該二維weight遞推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

其實就是把dp變成二維的，本質還是一樣的

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(String str: strs){    //遍歷物品int zeroNum = 0;int oneNum = 0;//得到每個物品的weight，分為0和1兩個維度for(char ch: str.toCharArray()){if(ch == '0'){zeroNum++;}else{oneNum++;}}for(int i = m; i>=zeroNum; i--){for(int j = n; j>=oneNum; j--){dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}

2.2 完全背包

理論基礎

區別于01背包：每件物品都可以放入背包無限次，可以重復放入

首先再回顧一下01背包的核心代碼

for(int i = 0; i < weight.size(); i++) { // 遍歷物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

我們知道01背包內嵌的循環是從大到小遍歷，為了保證每個物品僅被添加一次。

而完全背包的物品是可以添加多次的，所以要從小到大去遍歷，即：

// 先遍歷物品，再遍歷背包
for(int i = 0; i < weight.size(); i++) { // 遍歷物品for(int j = weight[i]; j <= bagWeight ; j++) { // 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

?且在純完全背包中，對于一維dp數組來說，其實兩個for循環嵌套順序是無所謂的！

例題：攜帶研究材料（完全背包）

public class Main {public static void main(String[] args) {int[] weight = {1,2,3,4};int[] value = {2,4,4,5};int bagSize = 5;// 創建dp數組int goods = weight.length;  // 獲取物品的數量int[] dp = new int[bagSize + 1];// 初始化dp數組,直接默認全為0// 填充dp數組，放不下的即j < weight[i]就默認不改變，一維數組直接繼承上一層無需賦值，簡化了代碼for (int i = 0; i < goods; i++) {for (int j = weight[i]; j <= bagSize; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bagSize]);}
}

LeetCode518：零錢兌換ii（求組合數）

不同面額的硬幣（可以重復使用）和一個總金額，求組合數

一個關鍵的知識點：

如果求組合數就是外層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];}
}

?LeetCode377：組合總和iv（求排列）

思路：同上，只是調一個for的順序，順序不同的序列被視作不同的組合所以是求排列

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target+1];dp[0] = 1;for(int i=0;i<= target;i++){for(int j=0;j<nums.length;j++){if(i >= nums[j])    dp[i] += dp[i-nums[j]];}}return dp[target];}
}

?LeetCode70：爬樓梯（求排列數）

思路：這其實就是完全背包的求排列數，秒啦

import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNextInt()){int n = sc.nextInt();int m = sc.nextInt();int[] dp = new int[n+1];dp[0] = 1;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){if(i>=j)    dp[i] += dp[i-j];}}System.out.println(dp[n]);}}
}

LeetCode322：零錢兌換（求最小數）

湊成目標的最小硬幣數量

思路：相比于LeetCode474：一和零是01背包求最大個數（二維weight）

這道題只不過改成了是完全背包求最小個數（weight就是數值）

這個初始化dp[0]=0，且由于求的是最小值，所以需要把所有dp一開始初始化為max才能進行比較

不多說了上代碼！

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount+1];//初始化dp數組為最大值for (int j = 0; j < dp.length; j++) {dp[j] = 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],dp[j-coins[i]]+1);}}return dp[amount]==max?-1:dp[amount];}
}

LeetCode279：完全平方數（求最小數）

思路：其實就是元素1-10的平方，給定target，上道題稍微改動一下就能過

class Solution {public int numSquares(int n) {int max = Integer.MAX_VALUE;int[] dp = new int[n+1];//初始化dp數組為最大值for (int j = 0; j < dp.length; j++) {dp[j] = max;}dp[0] = 0;for(int i=1;i<=10;i++){for(int j=i*i;j<=n;j++){//這個if是為了防止湊不成，而因為有1所以一定可以湊成，所以if可以略去if(dp[j-i*i]!= max) dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n]==max?-1:dp[n];}
}

LeetCode139：單詞拆分

判斷單詞是否可以被空格拆分為字典里的詞

思路：關于單詞拆分，回溯法也能做（這個再說）；如何轉換成背包呢？單詞即物品，字符串即背包，這道題就轉換成了物品是否能正好把背包裝滿。

1. dp[i]代表i前面的子串是否能由字典構成，true/false

2. 遞推：如果dp[j]==true && [j,i]子串也屬于字典則dp[i]==true（i<j）

3. 初始化:dp[0] =?true

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];HashSet<String> set = new HashSet<>(wordDict);dp[0] = true;for(int i=1;i<=s.length();i++){for(int j=0;j<i;j++){if(dp[j] == true && set.contains(s.substring(j,i))){//本身子字符串就不包含i，所以i就是下一個單詞開始的第一個字符dp[i] = true;}}}return dp[s.length()];}
}

2.3 多重背包

理論基礎

相當于n種物品和一個容量為v的背包，每種物品只有mi件，耗費空間ci，價值是wi

多重背包攤開可以變成01背包

例題：卡碼網56 攜帶礦石資源

import java.util.Scanner;
class multi_pack{public static void main(String [] args) {Scanner sc = new Scanner(System.in);/*** bagWeight:背包容量* n:物品種類*/int bagWeight, n;//獲取用戶輸入數據，中間用空格隔開，回車鍵換行bagWeight = sc.nextInt();n = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];int[] nums = new int[n];for (int i = 0; i < n; i++) weight[i] = sc.nextInt();for (int i = 0; i < n; i++) value[i] = sc.nextInt();for (int i = 0; i < n; i++) nums[i] = sc.nextInt();int[] dp = new int[bagWeight + 1];//先遍歷物品再遍歷背包，作為01背包處理for (int i = 0; i < n; i++) {for (int j = bagWeight; j >= weight[i]; j--) {//遍歷每種物品的個數for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) {dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}System.out.println(dp[bagWeight]);}
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/13398.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/13398.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/13398.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

vue uniapp 小程序 判斷日期是今天（顯示時分秒）、昨天、本周的周幾、超出本周顯示年月日

vue uniapp 小程序 判斷日期是今天（顯示時分秒）、昨天、本周的周幾、超出本周顯示年月日

效果圖&#xff1a; util.js /*** 轉換時間*/ const messageFormat (datetime) >{ let result "";let currentTime new Date();if(isToday(datetime)){result datetime.substring(11,16);}else if(isYesterday(datetime)){result "昨天";}else if(…
閱讀更多...
分層解耦-三層架構

分層解耦-三層架構

分層解耦-三層架構 Controller&#xff1a;控制層&#xff0c;接收前端發送的請求&#xff0c;對請求進行處理&#xff0c;并響應數據 service&#xff1a;業務邏輯層&#xff0c;處理具體的業務邏輯 dao&#xff1a;數據訪問層&#xff08;持久層&#xff09;&#xff0c;負…
閱讀更多...
python爬蟲[簡易版]

python爬蟲[簡易版]

python爬數據[簡易版] 對于每個網站的爬的原理基本是一樣的,但是具體的代碼寫法的區別就在于爬的數據中解析出想要的數據格式: 以爬取有道詞典中的圖片為例: 第一步:打開網站,分析圖片的數據源來自哪里, https://dict-subsidiary.youdao.com/home/content?invalid&pre…
閱讀更多...
操作系統磁盤管理類問題

操作系統磁盤管理類問題

例題&#xff1a;在磁盤上存儲數據的排列方式會影響1/0服務的總時間。假設每個磁道被劃分成10個物理塊&#xff0c;每個物理塊存放1個邏輯記錄。邏輯記錄R1,R2....R10存放在同一個磁道上&#xff0c;記錄的排列順序如下表所示&#xff1a; 假定磁盤的旋轉速度為10ms/周&#xf…
閱讀更多...
VMware虛擬機-安裝程序無法自動安裝virtual machine......_windows server 2008 R2

VMware虛擬機-安裝程序無法自動安裝virtual machine......_windows server 2008 R2

系統版本&#xff1a;windows server 2008 R2 問題-安裝程序無法自動安裝virtual machine… 在使用虛擬機安裝windows server 2008 R2系統中&#xff0c;安裝VMware Tools工具安祖啊寄給你失敗&#xff0c;提示安裝程序無法自動安裝virtual machine…&#xff0c;必須手動安裝…
閱讀更多...
從源頭到洞察：大數據時代的數據提取與分析實戰指南

從源頭到洞察：大數據時代的數據提取與分析實戰指南

隨著科技的飛速發展&#xff0c;大數據已經成為現代社會的核心驅動力之一。從商業決策到科學研究&#xff0c;從政策制定到個人生活&#xff0c;數據無處不在&#xff0c;影響著我們的每一個決策。然而&#xff0c;如何從海量的數據中提取有價值的信息&#xff0c;并轉化為深刻…
閱讀更多...
List類

List類

什么是 List 在集合框架中&#xff0c; List 是一個接口&#xff0c;繼承自 Collection 。 Collection 也是一個接口 &#xff0c;該接口中規范了后序容器中常用的一些方法&#xff0c;具體如下所示&#xff1a; List 中提供了好的方法&#xff0c;具體如下&#xff1a; List…
閱讀更多...
Conda 常用命令大全

Conda 常用命令大全

Conda 常用命令大全 配置源conda配置清華源pip配置清華源pip配置阿里源 環境管理創建一個新的虛擬環境列出虛擬環境激活虛擬環境退出虛擬環境刪除虛擬環境復制某個虛擬環境 conda包管理列出全部包安裝包卸載包 pip包管理列出全部包安裝包卸載包 其他命令查詢 conda 版本查看環境…
閱讀更多...
python發票真偽查驗開發文檔、票據OCR、數電票查驗

python發票真偽查驗開發文檔、票據OCR、數電票查驗

想象一下&#xff0c;只需一行行簡潔的代碼&#xff0c;復雜繁瑣的發票審核工作瞬間變得井然有序。翔云發票查驗開發文檔詳盡易懂&#xff0c;即便是Python新手也能迅速上手&#xff0c;搭建起自己的發票真偽查驗系統。無論是紙質發票的掃描圖像&#xff0c;還是電子發票的數據…
閱讀更多...
C語言詳解：數組指針

C語言詳解：數組指針

數組指針是指針 int* p[10] 這是指針數組的寫法 &#xff0c;因為【】的優先級比*高&#xff0c; 所以為了解決優先級問題&#xff0c;加&#xff08;&#xff09; int(* p)[10]&arr;//數組的地址要存起來 說明p是指針&#xff08;首先與*結合&#xff09;&#xff0c…
閱讀更多...
哈希表法快速求解最長連續序列 | 力扣128題詳細解析

哈希表法快速求解最長連續序列 | 力扣128題詳細解析

?????? 歡迎來到我的博客。希望您能在這里找到既有價值又有趣的內容&#xff0c;和我一起探索、學習和成長。歡迎評論區暢所欲言、享受知識的樂趣&#xff01; 推薦&#xff1a;數據分析螺絲釘的首頁 格物致知 終身學習 期待您的關注 導航&#xff1a; LeetCode解鎖100…
閱讀更多...
Oracle 數據庫 19c 選件和管理包 英文技術文檔

Oracle 數據庫 19c 選件和管理包 英文技術文檔

都是英文的&#xff0c;點擊鏈接可單獨下載。點這里批量下載。 Database Options&#xff1a; 數據庫選件或管理包數據表技術白皮書MultitenantData Sheet(12c)White PaperReal Application ClustersData Sheet(12c)White PaperActive Data GuardData Sheet(沒找到)White Pap…
閱讀更多...
關于電源3（整流濾波電路）

關于電源3（整流濾波電路）

整流濾波電路 框圖 一共有四種整流電路 以下是自己參考別人的文章https://blog.csdn.net/zhuguanlin121/article/details/130653498?ops_request_misc%257B%2522request%255Fid%2522%253A%2522171582622316800215096518%2522%252C%2522scm%2522%253A%252220140713.130102334…
閱讀更多...
jenkins配置不同版本nodeJS，保姆級叫你配置

jenkins配置不同版本nodeJS，保姆級叫你配置

問題描述&#xff1a;公司jenkins被改了nodejs版本適配其他項目導致以前的項目構建失敗&#xff0c;原因就是nodejs版本太高或太低導致&#xff0c;這里教大家不去更改服務器默認版本&#xff0c;當需要特殊版本直接在jenkins里配置即可。 過程 1、安裝nodeJS插件 1.1點擊管…
閱讀更多...
Linux中的nproc命令

Linux中的nproc命令

2024年5月15日&#xff0c;周三上午 nproc 是一個在類 Unix 系統中使用的命令行實用程序&#xff0c;用于返回系統上可用的處理器核心數量。這個數字通常比物理 CPU 核心的數量要少&#xff0c;因為它可能排除了超線程核心或熱插拔核心。nproc 命令讀取 /proc/cpuinfo 文件來獲…
閱讀更多...
怎么把照片變小做頭像？多種方法教你圖片改尺寸

怎么把照片變小做頭像？多種方法教你圖片改尺寸

現在在社交媒體平臺或者是社交軟件上&#xff0c;我們經常會去更改頭像來展示自己&#xff0c;但是有時候我們拍攝的照片太大無法直接用作頭像&#xff0c;這時候就需要去修改圖片尺寸&#xff0c;將圖片改大小到合適的數值才能使用&#xff0c;那么如何快速的將圖片改大小呢&a…
閱讀更多...
Ansys Mechanical｜中遠程點的Behavior該如何設置？

Ansys Mechanical｜中遠程點的Behavior該如何設置？

Remote point是ANSYS mechanical中的一種常見節點自由度耦合建模形式&#xff0c;在轉動裝配體中的連接轉動副、或者在施加遠端約束及遠端載荷的時候&#xff0c;我們經常用到遠端單元來耦合一個面或者一條線。例如銷軸似的滾動摩擦連接&#xff0c;如果我們希望將兩個物體通過…
閱讀更多...
TCP實現文件傳輸以及下載

TCP實現文件傳輸以及下載

目錄 1.上傳文件思路 2.下載文件思路 3.上傳文件代碼 4.下載文件代碼 5.運行格式 1.上傳文件思路 上傳文件就相當于客戶端發送文件 步驟&#xff1a; 創建套接字連接服務器獲取文件大小循環少量多次發送關閉文件和套接字 2.下載文件思路 下載文件就相當于服務器端接收…
閱讀更多...
layui+java前端傳json后端接收

layui+java前端傳json后端接收

項目場景&#xff1a; layui前端使用復選框選擇Table的數據傳到java后端進行業務操作 問題描述 報錯類型錯誤JSON轉換接收失敗的類型錯誤 解決方案&#xff1a; 分為前后端兩種情況 先說前端的: 前端需要是集合轉json下面是代碼案例 主界面的table選擇之后通過緩存傳到子界…
閱讀更多...
JavaScript 實現敏感信息脫敏

JavaScript 實現敏感信息脫敏

JavaScript 實現敏感信息脫敏 銀行卡號脫敏 要在 JavaScript 中對銀行卡信息進行脫敏&#xff0c;可以使用字符串處理方法來替換敏感信息為特定的字符。以下是一個簡單的示例代碼&#xff0c;將銀行卡號的中間數字用 “*” 替換&#xff1a; function desensitizeCardNumber…
閱讀更多...
最新文章

Copyright @ 2022~2023