本文主要是介绍代码随想录算法训练营第四十五天 爬楼梯 （进阶）、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];}
}
总结
-
我们要求的集合不强调是 组合 还是 排列 就先物品还是先背包没有要求
-
强调组合，先物品
-
强调排列，先背包
这篇关于代码随想录算法训练营第四十五天 爬楼梯 （进阶）、322. 零钱兑换、 279.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
