题号：70
难度：Easy
链接：https://leetcode.cn/problems/climbing-stairs/

思路

每次操作只有两种：爬一级或爬两级。

于是我将本体看作一个组合数问题，将两种操作看作红、黑球。由不同的总阶梯数，可以确定不同的操作(红、黑球)组合。而每一种操作组合可以有数种排列，求出每一种操作组合下的总的排列数量，即为题解。

代码

#include <math.h>

using std::min;

class Solution {
public:
    //我的思路
    int climbStairs(int n) {
        int count=0;
        int numOf_2=n/2;
        int i;
        for(int j=0;j<=numOf_2;++j){
            i = n - j*2;
            count += (i==0||j==0)?1:factorial_c((i+j),min(i,j));
        }
        return count;
    }
    //求组合数，n中取m
    long factorial_c(int n, int m){
        long fac_c=1;
        //每次乘上分子后除以一个分母，防止溢出
        for(int i=1;i<=m;++i){
            fac_c *= n-m+i;
            fac_c /= i;
        }
        return fac_c;
    }
};

提交结果

时间、空间表现都还不错。

但应当认识到，这种算法时间复杂度绝对在$O(n)$以上，甚至接近$O(n^2)$，提交能够达到0ms，一部分是因为LeetCode诡异的时间计算，一部分是因为数据量本身不大。并且，求组合数本身也很容易产生溢出，虽然在该部分做了少许优化防止溢出的发生，但在$n=45$的时候，就已经需要long型来存储中间结果了。

于是我打开评论区学习，果然找到了非常优雅永不过时的解法。

dalao解法

class Solution {
public:
    //动态规划解法
    int climbStairs(int n) {
        if(n<2) return n;
        int dp[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<n+1;++i) dp[i]=dp[i-1]+dp[i-2];
        return dp[n];
    }
};

这一解法的思想是，若要以一次操作登上$n$级台阶，有两种情况，一是从$n-1$级台阶以一步的操作到达，二是从$n-2$级台阶以两步的操作到达。

因此，登上$n$级台阶的操作组合总数，可以分为两部分，一部分是登上$n-1$级台阶的操作组合总数，另一部分是登上$n-2$级台阶的操作组合总数。

由此我们得到递推公式：$f(n)=f(n-1)+f(n-2)$。

故可以从前两层的情况得到第三层的情况，问题也就迎刃而解，并且时间复杂度在$O(n)$。

另外，虽然上述代码空间复杂度在$O(n)$，但也可以进一步优化至$O(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 <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

m为每次操作可以走的最大步数。

全文完

事实证明，写题还是得要草稿纸

今天写了三道Easy，里面两道都没Easy到哪里去~