算法刷题记录 Day39

算法刷题记录 Day39

Date: 2024.04.05

lc 279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
        // 完全背包问题
        // dp[j] 表示和为j的完全平方数的最少数量
        vector<int> dp(n+1, INT_MAX);
        // dp[j] = min(dp[j-i*i]+1, dp[j]);
        dp[0] = 0;
        for(int i=0; i<sqrt(n)+1; i++){
            for(int j=0; j<=n; j++){
                if(j >= i*i && dp[j-i*i] != INT_MAX){
                    dp[j] = min(dp[j-i*i]+1, dp[j]);
                }
            }
        }

        // 总能由1组成，不会无解。
        return dp[n];

    }
};

lc 322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 完全背包，组合问题
        // dp[j]表示能组成总金额j的最少硬币个数.为了防止递推值被覆盖，初始化为INT_MAX；
        vector<int> dp(amount+1, INT_MAX);
        // 递推起点初始化为0；
        dp[0] = 0;
        // dp[j] = for(i) dp[j] = min(dp[j], dp[j-coins[i]] +1);

        for(int i=0; i<coins.size(); i++){
            int tmp = coins[i];
            for(int j=0; j<=amount; j++){
                if(j >= tmp && dp[j-tmp] != INT_MAX){
                    dp[j] = min(dp[j], dp[j-tmp]+1);
                }
            }
        }
        if(dp[amount] != INT_MAX)
            return dp[amount];
        else
            return -1;
    }
};

kama 57. 爬楼梯

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    while(cin>>n>>m){
        std::vector<int> dp(n+1, 0);
        // dp[j]表示到达第i阶的方法数
        // dp[j] = for(i) dp[j] += dp[j-i];
        // 排列问题，先遍历背包，再遍历物品
        dp[0] = 1;
        for(int j=0; j<=n; j++){
            for(int i=1; i<=m; i++){
                if(j >= i)
                    dp[j] += dp[j-i];
            }
        }
        cout<<dp[n]<<endl;
    }    
    return 0;
}