Leetcode 70.爬楼梯

题目描述：

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

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

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

示例 1：

1
2
3
4
5

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

示例 2：

1
2
3
4
5
6

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

链接：

https://leetcode-cn.com/problems/climbing-stairs

题目分析

1.递归

  记得这道题是第一次学递归的时候就做的例题。爬 n 阶的楼梯，可以看做是爬了 n-1 阶的楼梯，最后一步再爬 1 个台阶；也可以看做是爬了 n-2 阶的楼梯，最后一步再爬 2 个台阶。而方法数就是这两种方法的和。这便是一个递归的过程，即有 $f(n)=f(n-1)+f(n-2)$。
  递归的终结条件是什么呢？还没开始爬的时候 $n=0$ 就是爬楼梯的开始，记为 1 种方法。而 $n=1$ 的时候，前一步只能爬 1 个台阶而不能爬 2 个台阶，因此方法数也是 1。
  PS：这种方法会超出时间限制。

1
2
3
4
5
6
7

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

  时间复杂度：$O(2^n)$，其中 $n$ 为楼梯的阶数。一共 $n$ 层递归，而每一层递归我们都需要调用两次递归函数。
  空间复杂度：$O(n)$，其中 $n$ 为楼梯的阶数。也即递归的深度。

2.动态规划

  递归的方法虽然容易理解，代码也十分简洁，但是其实时间复杂度非常高，即使是简单题也是毫不意外地超出了时间限制。这是因为每层递归都会调用两次递归函数，而且这个操作存在的大量的重复计算，比如 $f(n-1)$ 的计算中也需要用到 $f(n-2)$。如何复用这些函数的值呢？我们可以很容易想到动态规划。
  与递归相反，我们正向地推导这个过程。上面已经推出了状态转移方程 $f(n)=f(n-1)+f(n-2)$，起始条件也即 $f(0)=1$，$f(1)=1$。我们注意到状态转移只与前两个状态有关，而最后的结果是最后一个状态，则我们可以丢弃前面的状态，只用三个变量分别存储当前的状态、前一个状态、前两个状态。result 表示 $f(n)$，one 表示 $f(n-1)$，two 表示 $f(n-2)$。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int climbStairs(int n) {
        int result = 1, one = 0, two = 0;
        for(int i = 1; i <= n; i++){
            two = one;
            one = result;
            result = one + two;
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为楼梯的阶数。也即循环的次数。
  空间复杂度：$O(1)$。经过优化，我们只需要使用三个变量来进行状态转移，因此所需空间是常数级的。

3.数学方法

  通过前面的状态转移方程和初始值我们可以发现，其实这就是一个斐波那契数列。而通过 特征方程法 是可以得到斐波那契数列的通项公式的，也即 $a_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$。注意上面的通项公式是从 1 开始的，而我们的函数 $f$ 是从 0 开始的，因此在代入时需要将 n 加 1。

1
2
3
4
5
6

class Solution {
public:
    int climbStairs(int n) {
        return 1/sqrt(5)*(pow((1+sqrt(5))/2, n+1)-pow((1-sqrt(5))/2, n+1));
    }
};

  这个通项公式中包含了幂运算，具体时间复杂度取决于 CPU 的指令集，因此不分析。
  空间复杂度为 $O(1)$。

4.矩阵快速幂 - 官方题解

  来自于官方题解的方法，涉及了矩阵的知识。由于递推的关系可以视为矩阵相乘。

  则有

  因此我们需要计算的就是 $\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n$，可以将其拆分成 $\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{n/2}\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{n/2}$，以此类推。计算的时间复杂度是 $O(\log n)$，也即在较大的 $n$ 下，计算速度比动态规划更快。
  另外官方题解还提到了非齐次线性递推转化为矩阵快速幂的计算方法，上面的方法代码也包含其中。具体请阅读 爬楼梯 - 力扣官方题解。