70. 爬樓梯(進(jìn)階版)

一步一個(gè)臺(tái)階，兩個(gè)臺(tái)階，三個(gè)臺(tái)階，…，直到 m個(gè)臺(tái)階。問有多少種不同的方法可以爬到樓頂呢？

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

每一階可以重復(fù)使用，例如跳了1階，還可以繼續(xù)跳1階。

問跳到樓頂有幾種方法其實(shí)就是問裝滿背包有幾種方法。 求的是排列

class Solution {public int climbStairs(int n) {int[] dp = new int[n + 1];int m = 2; //m表示最多可以爬m(xù)個(gè)臺(tái)階dp[0] = 1;for (int i = 1; i <= n; i++) { // 遍歷背包for (int j = 1; j <= m; j++) { //遍歷物品if (i >= j)  //當(dāng)前的背包容量 大於 物品重量的時(shí)候，我們才需要記錄當(dāng)前的這個(gè)裝得方法（方法數(shù)+）dp[i] += dp[i - j];}}return dp[n];}
}

322. 零錢兌換

力扣題目鏈接

給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

你可以認(rèn)為每種硬幣的數(shù)量是無限的。

示例 1：

• 輸入：coins = [1, 2, 5], amount = 11
• 輸出：3
• 解釋：11 = 5 + 5 + 1

示例 2：

• 輸入：coins = [2], amount = 3
• 輸出：-1

示例 3：

• 輸入：coins = [1], amount = 0
• 輸出：0

示例 4：

• 輸入：coins = [1], amount = 1
• 輸出：1

示例 5：

• 輸入：coins = [1], amount = 2
• 輸出：2

提示：

• 1 <= coins.length <= 12

• 1 <= coins[i] <= 2^31 - 1

• 0 <= amount <= 10^4

• 動(dòng)規(guī)五部曲

1.確定dp數(shù)組以及下標(biāo)的含義

背包容量: 目標(biāo)值

硬幣:物品

問:裝滿這個(gè)背包,最少用多少件物品

dp[j]：湊足總額為j所需錢幣的最少個(gè)數(shù)為dp[j]

2.確定遞推公式

Math.min

dp[j]=Math.min(dp[j],dp[j-coins[i]]+1)

3.初始化

首先湊足總金額為0所需錢幣的個(gè)數(shù)一定是0，那么dp[0] = 0;

其他下標(biāo)對應(yīng)的數(shù)值呢？

考慮到遞推公式的特性，dp[j]必須初始化為一個(gè)最大的數(shù)，否則就會(huì)在Math.min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。

所以下標(biāo)非0的元素都是應(yīng)該是最大值。

//初始化dp數(shù)組為最大值for (int j = 0; j < dp.length; j++) {dp[j] = Integer.MAX_VALUE;}

4.遍歷順序求

求最小的元素?cái)?shù)量 ,不影響 都可以

5.打印dp數(shù)組

以輸入：coins = [1, 2, 5], amount = 5為例

代碼:

class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];//初始化 其他下標(biāo)  因?yàn)橐笞钚∷圆荒苜x值為0  會(huì)被覆蓋for (int j = 0; j < dp.length; j++) {dp[j] = Integer.MAX_VALUE;}dp[0]=0;for(int i=0;i<coins.length;i++){  //遍歷物品for(int j=coins[i];j<=amount;j++){  //遍歷背包if(dp[j - coins[i]] != Integer.MAX_VALUE){// 如果dp[j - coins[i]]是初始值則跳過dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];}
}

279.完全平方數(shù)

力扣題目鏈接

給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, …）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。

給你一個(gè)整數(shù) n ，返回和為 n 的完全平方數(shù)的 最少數(shù)量 。

完全平方數(shù) 是一個(gè)整數(shù)，其值等于另一個(gè)整數(shù)的平方；換句話說，其值等于一個(gè)整數(shù)自乘的積。例如，1、4、9 和 16 都是完全平方數(shù)，而 3 和 11 不是。

示例 1：

• 輸入：n = 12
• 輸出：3
• 解釋：12 = 4 + 4 + 4

示例 2：

• 輸入：n = 13
• 輸出：2
• 解釋：13 = 4 + 9

提示：

• 1 <= n <= 10^4

• 動(dòng)態(tài)規(guī)劃五部曲

1.確定dp數(shù)組的含義

背包容量: 整數(shù)n

物品:完全平方數(shù) i*i

問題:給你一個(gè)整數(shù) n ，返回和為 n 的完全平方數(shù)的 最少數(shù)量 。

dp[j]: 和為j時(shí),完全平方數(shù)最少的數(shù)量為dp[j]

2.確定遞推公式

dp[j]=Math.min(dp[j],dp[j-i*i]+1)

每個(gè)元素的數(shù)值用i*i表示

3.初始化

首先湊足總金額為0所需錢幣的個(gè)數(shù)一定是0，那么dp[0] = 0;

其他下標(biāo)對應(yīng)的數(shù)值呢？

考慮到遞推公式的特性，dp[j]必須初始化為一個(gè)最大的數(shù)，否則就會(huì)在Math.min(dp[j - coins[i]] + 1, dp[j])比較的過程中被初始值覆蓋。

所以下標(biāo)非0的元素都是應(yīng)該是最大值。

//初始化dp數(shù)組為最大值for (int j = 0; j < dp.length; j++) {dp[j] = Integer.MAX_VALUE;}

4.遍歷順序求

求最小的元素?cái)?shù)量,不影響

5.打印dp數(shù)組

已輸入n為5例，dp狀態(tài)圖如下：

dp[0] = 0 dp[1] = min(dp[0] + 1) = 1 dp[2] = min(dp[1] + 1) = 2 dp[3] = min(dp[2] + 1) = 3 dp[4] = min(dp[3] + 1, dp[0] + 1) = 1 dp[5] = min(dp[4] + 1, dp[1] + 1) = 2

最后的dp[n]為最終結(jié)果。

代碼：

class Solution {public int numSquares(int n) {int[] dp=new int[n+1];for(int j=0;j<=n;j++){dp[j]=Integer.MAX_VALUE;}dp[0]=0;for(int i=1;i*i<=n;i++){  //遍歷物品for(int j=i*i;j<=n;j++){   //遍歷背包  背包從物品大小開始dp[j]=Math.min(dp[j],dp[j-i*i]+1);  //為了下標(biāo)不出現(xiàn)負(fù)數(shù)}}return dp[n];}
}