问题

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

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

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

示例 1：

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

1 阶 + 1 阶2 阶

示例 2：

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶1 阶 + 2 阶2 阶 + 1 阶

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/climbing-stairs

解法

一、递归法

题目分析：

如果从第0级台阶爬到第1级台阶：有1种方法（爬1个台阶）如果从第0级台阶爬到第2级台阶：有2种方法（爬1个台阶 或 爬2个台阶）如果从第0级台阶爬到第3级台阶：有3种方法 先从第0级台阶爬到第1级台阶，再从第1级台阶爬到2级台阶，再从第2级台阶爬到第3级台阶，即1,1,1先从第0级爬1个台阶到第1级台阶，再从第1级爬2个台阶到第3级，即1,2先从第0级爬2个台阶到第2级台阶，再从第2级爬1个台阶到第3级，即2,1 如果从第0台阶爬到第4级台阶：有5种方法 1,1,1,11,1,21,2,12,1,12,2 如果从第0台阶爬到第5级台阶，有8种方法（这里懒得列了，你可以试试）

转换成数学的逻辑题，很容易看得出来：

f(1)=1

f(2)=2

f(3)=3

f(4)=5

f(5)=8

f(6)=13

f(7)=21

即1,2,3,5,8,13,21

可以发现，除了第一个数和第二个数外，从第三个数开始，他前面两个数的和就是他自身。

相当于

第三个数（3）= 第一个数（1）+ 第二个数（2）

第四个数（5）= 第二个数（2）+ 第三个数（3）

第五个数（8）= 第三个数（3）+ 第四个数（5）

可得出：第n个数 = 第(n-2)个数 + 第(n-1)个数

写成递推公式则是：f(n) = f(n-2)+f(n-1)

这样即可使用递归来解决。

代码如下：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { //如果是爬到第1级台阶，直接返回1 //如果是爬到第2级台阶，直接返回2 if ($n === 1 || $n === 2) { return $n; } //如果是爬到>2级的台阶，则按照递推公式，使用递归返回 return $this->climbStairs($n - 2) + $this->climbStairs($n - 1); } }

提交一下：

这就很尴尬了，无疑，使用递归是能够实现的，但是时间却过长。

优化下递归：

以爬到第5级台阶为例，可以得出以下递归二叉树图 在递归中，计算第5级台阶的方法数时，便需要计算第4级台阶的方法数和第3级台阶的方法数；

而在计算第4级台阶的方法数时，是计算了第3级台阶的方法数和***第2级台阶的方法数***

在计算第3级台阶的方法数是，是计算了第1级台阶的方法数，并重复计算了***第2级台阶的方法数***

当然，同样被重复不止第2级台阶的方法数，哪怕在上面，第3级台阶的方法数和第1级台阶的方法数也是被重复计算了的

重复计算无异于提高了时间复杂度，这里，可考虑使用记忆数组，来记录已经计算过的第n级方法数，避免重复计算，将将时间复杂度优化到O(n)

代码如下：

class Solution { //记忆数组，记录已经计算过的结果数据，避免重复计算，减少时间复杂度 private $momeryArr = []; /** * @param Integer $n * @return Integer */ function climbStairs($n) { //如果已经有记忆了的计算结果，直接返回 if (isset($this->momeryArr[$n])) { return $this->momeryArr[$n]; } //如果是爬到第1级台阶，直接返回1 //如果是爬到第2级台阶，直接返回2 if ($n === 1 || $n === 2) { //将计算结果记录下来 $this->momeryArr[$n] = $n; return $n; } //如果是爬到>2级的台阶，则按照递推公式，使用递归返回 //将计算结果记录下来 $this->momeryArr[$n] = $this->climbStairs($n - 2) + $this->climbStairs($n - 1); return $this->momeryArr[$n]; } }

这样就提交成功，不超时了

二、动态规划法

按照递归的题解思路，我们已经得到递推公式：

当n=1时，f(n) = 1当n=2时，f(n) = 2当n=3时，f(n) = f(n-1) + f(n-2)

代码如下：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { //如果是爬到第1级台阶，直接返回1 //如果是爬到第2级台阶，直接返回2 if ($n === 1 || $n === 2) { //将计算结果记录下来 return $n; } $climbStairs[1] = 1; //f(1)=1 $climbStairs[2] = 2; //f(2)=2 //所要计算的内容，将计算结果保存到数组$climbStairs中，最终得到f(n) for ($i = 3; $i <= $n; $i++) { $climbStairs[$i] = $climbStairs[$i - 1] + $climbStairs[$i - 2]; // f(n) = f(n-1) + f(n-2) } //得到最终结果 return $climbStairs[$n]; } }

使用滚动数组的逻辑来处理：使用三个变量$first、$second、$third，来取代$climbStairs数组。当n=1和n=2时，按照原逻辑返回即可。

当n=5时，我们先计算n=3的值，再计算n=4的值，再把两者相加

先默认$first=1,$second=2，对应f(1)和f(2)求f(3)时，即是$third=$first+$second，f(3)便是$third求f(4)时，我们也要实现f(4)=$first+$second，这样才能减少空间复杂度。那么，$first就应是f(2)，$second就应是f(3)。所以在上一步时，就应该将两者的值给替换成上述情况。回到求f(3)时的情景。在得到$third后，应该将$second的值给$first，$third的值给$second，这样，$first就一直是f(n-2)，$third是f(n-1)最后，求f(5)，也是同样的$third=$first+$second即能得到结果，循环也应到此结束，返回所求的f(5)的值

代码如下：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { //如果是爬到第1级台阶，直接返回1 //如果是爬到第2级台阶，直接返回2 if ($n === 1 || $n === 2) { //将计算结果记录下来 return $n; } $first = 1; //f(1)=1 $second = 2; //f(2)=2 //所要计算的内容，将计算结果保存到数组$climbStairs中，最终得到f(n) for ($i = 3; $i <= $n; $i++) { $third = $first + $second; // f(n) = f(n-1) + f(n-2) $first = $second; //更新$first的值，让下一次循环时，它是f(n-2) $second = $third; //更新$second的值，让下一次循环时，它是f(n-1) } //得到最终结果 return $third; } }

三、矩阵法

首先，来了解温习一下：矩阵的乘法

两个矩阵的乘法仅当第一个矩阵A 的列数和另一个矩阵 B 的行数相等时才能定义。如A是m×n矩阵和B是n×p矩阵，他们的乘积C是一个m×p矩阵 $$C=(c_{ij})$$ 它的一个元素： $$c_{i,j}=a_{i,1}{b}_{1,j}+a_{i,2}{b}_{2,j}+\cdots +a_{i,n}{b}_{n,j}=\sum _{r=1}^n{a}_{i,r}br,j$$ 并将此乘积记为: $$C=AB$$ 例如： $$\left[\begin{array}{ccc}1& 0& 2\\ -1& 3& 1\end{array}\right]\times \left[\begin{array}{cc}3& 1\\ 2& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}(1\times 3+0\times 2+2\times 1)& (1\times 1+0\times 1+2\times 0)\\ (-1\times 3+3\times 2+1\times 1)& (-1\times 1+3\times 1+1\times 0)\end{array}\right]=\left[\begin{array}{cc}5& 1\\ 4& 2\end{array}\right]$$ 矩阵的乘法满足以下运算律：

结合律： $$(AB)C=A(BC)$$ 左分配律： $$(A+B)C=AC+BC$$ 右分配律： $$C(A+B)=CA+CB$$ 矩阵乘法不满足交换律。

从上述解题思路已知： $$F_{n+1}=F_n+F_{n-1}$$ 现在回到题目，首先我们可以构建这样一个递推关系： $$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\times \left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]=\left[\begin{array}{c}f(n)+f(n-1)\\ f(n)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$ 因此可得 $$\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\times \left[\begin{array}{c}f(1)\\ f(0)\end{array}\right]$$ 而f(1)=1，f(0)=0，进行公式转换 $${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\times \left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{cc}m00& m01\\ m10& m11\end{array}\right]\times \left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}m00\\ m10\end{array}\right]$$ 也就是，所求的n位置的方法数(fn)，即 $${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n$$ 获取其矩阵左下角m10

代码如下：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { $m = [ [1, 1], [1, 0] ]; //计算$m的n次幂 $res = $this->pow($m, $n); //返回$m矩阵的左下角元素$m10 return $res[1][0]; } /** * @title 计算矩阵$a的n次幂 * @param $a * @param $n * @return array|mixed */ function pow($a, $n) { $ret = [ [0, 1], [1, 0] ]; //使用二分法获取 while ($n > 0) { if (($n & 1) == 1) { $ret = $this->multiply($ret, $a); } $n >>= 1; $a = $this->multiply($a, $a); } return $ret; } /** * @title 计算两个两行两列的矩阵的积 * @param $a * @param $b * @return mixed */ function multiply($a, $b) { for ($i = 0; $i < 2; $i++) { for ($j = 0; $j < 2; $j++) { $c[$i][$j] = $a[$i][0] * $b[0][$j] + $a[$i][1] * $b[1][$j]; } } return $c; } }

四、通项公式

之前的方法我们已经讨论了 f(n)f(n) 是齐次线性递推，根据递推方程 f(n) = f(n - 1) + f(n - 2)，我们可以写出这样的特征方程： $$x^2=x+1$$ 求得 $$x_1=\frac{1+\sqrt{5}}{2}$$ $$x_2=\frac{1-\sqrt{5}}{2}$$ 设通解为 $$f(n)=c_1{x}_1^n+c_2{x}_2^n$$ 代入初始条件f(1)=1，f(2)=1，可得 $$c_1=\frac{1}{\sqrt{5}}$$ $$c_2=-\frac{1}{\sqrt{5}}$$ 得到递推数列的通项公式 $$f(n)=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]$$ 接着我们就可以通过这个公式直接求第 n 项了。

代码如下：

class Solution { /** * @param Integer $n * @return Integer */ function climbStairs($n) { //套用通用公式进行计算 $sqrt5 = sqrt(5); $fibn = pow((1 + $sqrt5) / 2, $n + 1) - pow((1 - $sqrt5) / 2, $n + 1); return (int)($fibn / $sqrt5); } }

以上便是“爬楼梯”的各种解法，不得不说，人类的智慧是无穷的，这里搬砖外加自己理解总结，希望能够让你也有所提高。

参考文章：LeetCode-Solution