算法训练day50卡玛70. 爬楼梯（进阶版）Leetcode322. 零钱兑换279. 完全平方数

57. 爬楼梯（第八期模拟笔试）

题目分析

我们可以使用动态规划。动态规划的思想是用一个数组dp来保存到达每一级台阶的方法数。对于每一级台阶i，你可以从i-1, i-2, ..., i-m级台阶爬上来（只要这些台阶的索引大于等于0），因此到达第i级台阶的方法数就是这些dp[j]（i-m <= j < i）的总和。

acm代码模式

#include <iostream>
#include <vector> 

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if(i - j >= 0) dp[i] += dp[i -j];   
        }
    }
    
    // for (int i : dp) std::cout << i << " ";
    std::cout << dp[n] << std::endl;
    return 0;
}

322. 零钱兑换

题目分析

本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！

acm模式代码

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

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

int main() {
    Solution sol;
    std::vector<int> coins = {1, 2, 5};
    int res = sol.coinChange(coins, 11);
    std::cout << std::endl;
    std::cout << res << std::endl;
    return 0;
}

279. 完全平方数

题目分析

• 创建了一个大小为n + 1的数组dp，所有元素初始化为INT32_MAX，这表示对于每个目标值来说，初始状态下所需的完全平方数数量是未知的，假定为无限大。
• dp[0] = 0意味着和为0的数字最少需要0个完全平方数（即没有数字时的情况）。
• 外循环遍历从1到n的所有数字，代表当前考虑的目标和。
• 内循环尝试所有可能的完全平方数，即所有小于等于当前目标和i的完全平方数。
• 对于每一个i和j，如果i大于或等于j的平方，那么dp[i]（即组成和为i的最少完全平方数的数量）可以通过查看dp[i - j*j] + 1来更新。+1是因为j*j是当前考虑的一个完全平方数，而dp[i - j*j]则代表了减去这个完全平方数之后剩余部分的最优解。
• 最终，dp[i]会被更新为所有可能的j中的最小值。

acm模式代码

#include <iostream>
#include <vector>

class Solution {
public:
    int numSquares(int n) {
        std::vector<int> dp(n + 1, INT32_MAX);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= n; j ++) 
                if(i - j*j >= 0) dp[i] = std::min(dp[i - j*j] + 1, dp[i]);
        }

        for (int i: dp) {
            std::cout << i << " " ;
        }

        return dp[n];
    }
};

int main() {
    Solution sol;
    sol.numSquares(12);
    return 0;
}