题目: 爬楼梯

分析

方法一：暴力递归

首先，我们可以使用递归的方法来解决该问题。具体地，我们定义一个递归函数 climbStairs(n)，它表示爬上 n 阶楼梯的不同方法数。因为每次我们可以选择爬一阶或者两阶楼梯，所以我们可以把问题转化为求爬上 n - 1 阶楼梯和 n - 2 阶楼梯的不同方法数之和，即 climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)。当 n = 1 或 n = 2 时，显然有 climbStairs(n) = n。该递归函数的时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$，会超时。

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

方法二：动态规划 我们可以使用动态规划的方法来优化上述递归算法，以减小时间复杂度。具体来说，我们定义一个长度为 n+1 的数组 dp，其中 dp[i] 表示爬到第 i 阶楼梯的不同方法数。显然有 dp[1] = 1，dp[2] = 2。对于 i > 2 的情况，由于我们每次可以选择爬一阶或者两阶楼梯，因此到达第 i 阶楼梯的方法数为到达第 i-1 阶楼梯的方法数和到达第 i-2 阶楼梯的方法数之和，即 dp[i] = dp[i-1] + dp[i-2]。最终 dp[n] 即为所求。该算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int pre1 = 1, pre2 = 2, cur = 0;
        for (int i = 3; i <= n; i++) {
            cur = pre1 + pre2;
            pre1 = pre2;
            pre2 = cur;
        }
        return cur;
    }
};

方法三：斐波那契数列公式 我们还可以使用斐波那契数列公式来解决该问题。具体地，我们可以使用公式 $F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$，其中 $\frac{1+\sqrt{5}}{2}$ 和 $\frac{1-\sqrt{5}}{2}$ 分别是斐波那契数列的两个根。使用该公式，我们可以直接求得第 n 个斐波那契数 $F_n$，进而计算出爬上 n 阶楼梯的不同方法数。该算法的时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<vector<int>> matrix = {{1, 1}, {1, 0}};
        vector<vector<int>> res = matrixPower(matrix, n - 2);
        return 2 * res[0][0] + res[1][0];
    }
    
    vector<vector<int>> matrixPower(vector<vector<int>> &matrix, int p) {
        vector<vector<int>> res(matrix.size(), vector<int>(matrix.size(), 0));
        for (int i = 0; i < matrix.size(); i++) {
            res[i][i] = 1;
        }
        vector<vector<int>> tmp = matrix;
        for (; p; p >>= 1) {
            if (p & 1) res = matrixMultiply(res, tmp);
            tmp = matrixMultiply(tmp, tmp);
        }
        return res;
    }
    
    vector<vector<int>> matrixMultiply(vector<vector<int>> &a, vector<vector<int>> &b) {
        vector<vector<int>> res(a.size(), vector<int>(b[0].size(), 0));
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b[0].size(); j++) {
                for (int k = 0; k < b.size(); k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
};