● 70. 爬樓梯 （進階）

思路：- 排列 先value后weight

代碼：

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

● 322. 零錢兌換

思路：

代碼

class Solution {public int coinChange(int[] coins, int amount) {// int n=coins.length;int[] dp=new int[amount+1];dp[0]=0;for(int i=1;i<=amount;i++){dp[i]=Integer.MAX_VALUE/2;// 除 2 是防止下面 + 1 溢出}for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}return dp[amount]==Integer.MAX_VALUE/2?-1:dp[amount];}
}

或者

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;}//當金額為0時需要的硬幣數目為0dp[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];}
}

● 279.完全平方數

思路：

代碼

class Solution {// 版本一，先遍歷物品, 再遍歷背包public int numSquares(int n) {int max = Integer.MAX_VALUE;int[] dp = new int[n + 1];//初始化for (int j = 0; j <= n; j++) {dp[j] = max;}//如果不想要寫for-loop填充數組的話，也可以用JAVA內建的Arrays.fill()函數。//Arrays.fill(dp, Integer.MAX_VALUE);//當和為0時，組合的個數為0dp[0] = 0;// 遍歷物品for (int i = 1; i * i <= n; i++) {// 遍歷背包for (int j = i * i; j <= n; j++) {//if (dp[j - i * i] != max) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);//}//不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。}}return dp[n];}
}