算法训练营Day45(完全背包）

 70. 爬楼梯 （进阶）

题目页面 (kamacoder.com)

完全背包的排列问题

import java.util.Scanner;
class Main{public static void main(String [] args){Scanner sc = new Scanner(System.in);int m,n;while(sc.hasNextInt()){n = sc.nextInt();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]);}} 
}

 322. 零钱兑换 

322. 零钱兑换 - 力扣（LeetCode）

class Solution {public int coinChange(int[] coins, int amount) {//装满容量为j的背包，最少物品为dp[j] 求dp[amount]int [] dp = new int[amount+1];//初始化，递推公式+1得到的数，初始0,非0下标，int最大值for(int i = 1;i<dp.length;i++){dp[i] = 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) {//递推公式，数量，所以+1dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount] ==Integer.MAX_VALUE?-1:dp[amount];}
}

279.完全平方数 

本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做 

279. 完全平方数 - 力扣（LeetCode）

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;}dp[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];}
}