算法训练营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) {
                    //递推公式，数量，所以+1
                     dp[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];
    }
}