算法题打卡day45-背包问题 | 70. 爬楼梯（进阶）、322. 零钱兑换、279.完全平方数-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法题打卡day45-背包问题 | 70. 爬楼梯（进阶）、322. 零钱兑换、279.完全平方数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

70. 爬楼梯 - 力扣（LeetCode）

状态：查看思路后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];
    }
};

322. 零钱兑换 - 力扣（LeetCode）

状态：查看思路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];
    }
};

279. 完全平方数 - 力扣（LeetCode）

状态：查看思路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];
    }
};

先背包，再物品：文章来源地址https://www.toymoban.com/news/detail-680668.html

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];
    }
};

到了这里，关于算法题打卡day45-背包问题 | 70. 爬楼梯（进阶）、322. 零钱兑换、279.完全平方数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！