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

目录

一、（leetcode 70）爬楼梯

二、（leetcode 322）零钱兑换

三、（leetcode 279）完全平方数

---

一、（leetcode 70）爬楼梯

力扣题目链接​​​​​​

状态：查看思路后AC

除了常规的可以爬一或二级台阶，当题目稍微修改一下，变成可以爬m级台阶，之前的DP思路就有局限（dp[i] = dp[i-1] + dp[i-2），为了通杀这类问题，可以将题目转换为完全背包问题，可以爬的楼梯级数就是背包中的物品，楼梯总数就是背包，注意例如五级台阶1，2，2和2，2，1是不同的方法，所以类比昨天的组合总数问题，需要先遍历背包，再遍历物品、

class Solution {
public:int climbStairs(int n) {// 转换为完全背包问题vector<int> dp(n+1, 0);dp[0] = 1;for(int i = 1; i <= n; ++i){ // 先背包for(int j = 1; j <= 2; ++j){ // 后物品（可以爬的台阶数，题目中是2）if(i-j >= 0) dp[i] += dp[i-j];}}return dp[n];}
};

二、（leetcode 322）零钱兑换

力扣题目链接

状态：查看思路Debug后AC。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1, INT_MAX);dp[0] = 0;int len = coins.size();for(int i = 0; i < len; ++i){for(int j = coins[i]; j <= amount; ++j){if(dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j], dp[j-coins[i]]+1);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

三、（leetcode 279）完全平方数

力扣题目链接

状态：查看思路Debug后AC。

注意转换为完全背包后的先物品再背包和先背包再物品的遍历方式在实现上的细节问题，这里将两种代码都放上。

先物品，再背包：

class Solution {
public:int numSquares(int n) {// 完全平方数就是物品，总和就是背包，转换成一个无重复组合的完全背包问题vector<int> dp(n+1, INT_MAX);dp[0] = 0;for(int i = 1; i*i <= n; ++i){// 先物品for(int j = i*i; j <= n; ++j){dp[j] = min(dp[j], dp[j - i*i]+1);}}return dp[n];}
};

先背包，再物品：

class Solution {
public:int numSquares(int n) {// 完全平方数就是物品，总和就是背包，转换成一个无重复组合的完全背包问题vector<int> dp(n+1, INT_MAX);dp[0] = 0;for(int i = 0; i <= n; ++i){// 先背包for(int j = 1; j*j <= i; ++j){if(dp[i - j*j] != INT_MAX){dp[i] = min(dp[i], dp[i - j*j]+1);}}}return dp[n];