代码随想录Day50 | 70. 爬楼梯 322. 零钱兑换 279.完全平方数

70.爬楼梯

文档讲解：代码随想录
视频讲解：
状态

1. dp数组 dp[j]表示爬上第j阶台阶需要的方法数
2. 递推公式，由于在每一阶台阶可以向上走1~m阶，所以到达第j阶台阶，是所有可以走到的台阶之和

dp[j] += dp[j-i]

3. 初始化
   应当将第0阶台阶初始化为1
4. 遍历顺序
   这其实是一个排列问题，即先上1阶与先上2阶是不同的方法，所以应当先遍历背包即当前台阶位置。而每一阶涉及到重复选择之前的台阶，所以对于背包的遍历需要从前向后
5. 打印dp

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    int total, climb;
    cin >> total >> climb;
    
    vector<int> dp(total+1);
    dp[0] = 1;
    for(int j = 1;j<=total;j++)
    {
        for(int i = 1;i<=climb;i++)
        {
            if(j>=i)
            {
                dp[j] += dp[j-i];
            }
        }
    }
    cout << dp[total];
    return 0;
}

322.零钱兑换

文档讲解：代码随想录
视频讲解： 装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换
状态

相较于之前的零钱兑换问题，数组中的每个元素可以重复选择所以是一个完全背包问题，而由于求的是最少的钱币个数所以可以理解为一个组合也可以是一个排列。那么背包和物品的遍历顺序就没有影响

1. dp数组
   dp[j] 表示 能够组成j的最少个数
2. 递推公式
   那么就是当前的个数和j-nums[i]这个和的最少个数+1相互比较

dp[j] = min(dp[j] ,dp[j-nums[i]]+1)

3. 初始化
   求最小值那么需要将每个值先初始化为最大值，而对于和为0的组合dp[0] = 0
4. 遍历顺序
   背包从头向后， 先背包或者先物品
5. 打印dp

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        //组合问题
        for(int i = 0;i<coins.size();i++)
        {
            for(int j = 1;j<=amount;j++)
            {
            //跳过之前没有成立的结果
                if(j>=coins[i] && 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：279.完全平方数
状态

1. dp数组
   dp[j] 表示 数j可以由最少的完全平方数组成的个数
2. 递推公式

dp[j] = min(dp[j],dp[j-i*i]+1);

3. 初始化
   同样需要初始化为最大值 dp[0] = 0。
4. 遍历顺序
   完全平方数可以重复选择是一个完全背包问题，背包的遍历顺序从头到尾，而对于最少个数问题不需要考虑组合或者排列所以可以随便选择遍历先后
5. 打印dp

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++)
            {
                if(dp[j-i*i] != INT_MAX)
                {
                    dp[j] = min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
};