训练营四十五天 | ● 70. 爬楼梯 （进阶）● 322. 零钱兑换 ● 279.完全平方数

70. 爬楼梯 （进阶） 

一次跨1-m个台阶为物品，共有n个台阶为背包容量，排列问题，完全背包

代码随想录

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 = 1; i <= m; i++) {//物品
                if(j >= i) {
                    dp[j] += dp[j - i];
                }
            }
        }
        System.out.println(dp[n]);
    }
}

 322. 零钱兑换  

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

本题求零钱个数，组合和排序都可以

注意初始化 递推公式

凑不齐就跳过

代码随想录

先背包再物品 排列

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];int max = Integer.MAX_VALUE;//求最小个数，初始化最大值，使之不能被覆盖for(int j = 0; j <= amount;j++) {dp[j] = max;}dp[0] = 0;//当总金额为0时，不取钱，钱的个数为0， 其他金额的初始值为maxfor(int j = 0; j <= amount; j++) {//背包zhengxufor(int i = 0; i < coins.length; i++) {//物品if(j >= coins[i] && dp[j - coins[i]] != max) {//跳过最大值，因为最大值不能被满足，永远凑不齐dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);//取小值}}}return dp[amount] == max ? -1 : dp[amount];//若dp[amount] 为max时，凑不齐，返回-1，其他时候返回dp[amount]}
}

先物品再背包 组合

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];int max = Integer.MAX_VALUE;//求最小个数，初始化最大值，使之不能被覆盖for(int j = 0; j <= amount;j++) {dp[j] = max;}dp[0] = 0;//当总金额为0时，不取钱，钱的个数为0， 其他金额的初始值为maxfor(int i = 0; i < coins.length; i++) {for(int j = coins[i]; j <= amount; j++) {if(dp[j - coins[i]] != max) {//跳过最大值，因为最大值不能被满足，永远凑不齐dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);//取小值}}}return dp[amount] == max ? -1 : dp[amount];//若dp[amount] 为max时，凑不齐，返回-1，其他时候返回dp[amount]}
}

 279.完全平方数  

区别在于不用判断是否能凑齐 因为有1 必然凑齐

代码随想录