代码随想录算法训练营第四十五天爬楼梯（进阶）、322. 零钱兑换、 279.完全平方数

本文主要是介绍代码随想录算法训练营第四十五天爬楼梯（进阶）、322. 零钱兑换、 279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第四十五天 | 爬楼梯（进阶）、322. 零钱兑换、 279.完全平方数

二维爬楼梯（进阶）

题目链接：题目页面 (kamacoder.com)

爬楼梯的高度n就是背包的容量

每次能爬1 ~ m阶台阶，说明1 ~ m的就是物品的种类

这样就把题目变成了一个完全背包问题：

从1~m中任选（无线数量）求凑成n一共有多少种排列方式？

dp[0]需要初始化为

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. 零钱兑换

题目链接：322. 零钱兑换 - 力扣（LeetCode）

不理解的是，为什么不强调组合还是排列就能不在意遍历顺序？

class Solution {public int coinChange(int[] coins, int amount) {if(coins.length == 0){return -1;}int[] dp = new int[amount+1]; // dp[i] 表示凑成金额 i 所需的最少硬币数Arrays.fill(dp, amount + 1); // 将 dp 数组初始化为一个较大的值，确保在后续更新中可以正确比较最小值。dp[0] = 0;  // 凑成金额 0 不需要硬币// 对本题来说，要求的是并不强调集合是 组合 还是 排列！// 所以先遍历 物品 或者 背包都是可行的for(int i = 0; i < coins.length; ++i) {for(int j = coins[i]; j < amount + 1; ++j) {if(dp[j - coins[i]] != amount + 1) {dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount]; // 表示如果凑成总金额的最少硬币数仍然是初始时的较大值，说明无法凑成总金额}
}

279.完全平方数

题目链接：279. 完全平方数 - 力扣（LeetCode

就是零钱兑换。

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, n + 1);dp[0] = 0;for(int i = 0; i <= Math.sqrt((double) n); ++i) {for(int j = i * i; j <= n; ++j) {if(dp[j - i * i] != n + 1) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}return dp[n] > n ? -1 : dp[n];}
}