题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

样例

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

算法1

(动态规划) $O(n)$

$f[i]$代表爬到第$i$阶的方法的集合，属性为方法数量；
最后一步可能是爬1阶或者2阶，所以$f[i] = f[i - 1] + f[i - 2]$

时间复杂度

$O(n)$个$O(1)$时间的转移，所以总时间复杂度为$O(n)$

参考文献

C++ 代码

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        vector<int> f(n + 1);
        f[0] = f[1] = 1;

        for (int i = 2; i <= n; ++i)
            f[i] = f[i - 1] + f[i - 2];

        return f[n];
    }
};

优化空间版本

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        int f0 = 1, f1 = 1, tmp;

        for (int i = 2; i <= n; ++i){
            tmp = f0 + f1;
            f0 = f1;
            f1 = tmp;
        }

        return f1;
    }
};

算法2

(矩阵快速幂) $O(logn)$

我们有通项公式，$a_k = a_{k - 1} + a_{k - 2}$，可以将其转化为矩阵形式。

时间复杂度

矩阵快速幂时间复杂度为$logn$。

参考文献

C++ 代码

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        return mat_pow({{1, 1}, {1, 0}}, n)[0][0];
    }

    vector<vector<long long>> mat_mul(vector<vector<long long>> &A, vector<vector<long long>> &B){
        int m = A.size(), n = A[0].size(), p = B[0].size();
        vector<vector<long long>> res(m, vector<long long>(p));

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < p; ++j)
                for (int k = 0; k < n; ++k)
                    res[i][j] += A[i][k] * B[k][j];

        return res;
    }

    vector<vector<long long>> mat_pow(vector<vector<long long>> mat, int n){
        if (n == 0) return {{1, 0}, {0, 1}};
        vector<vector<long long>> res = {{1, 0}, {0, 1}};

        while (n > 0){
            if (n & 1) res = mat_mul(res, mat);
            mat = mat_mul(mat, mat);
            n >>= 1;
        }

        return res;
    }
};