题目描述
我们来看看力扣的一道经典问题70. 爬楼梯
递归
假设n级台阶有climbStairs(n)种方法爬到楼梯顶。如果有n级台阶，如果第一次往上爬1级台阶，就会剩下n-1级台阶，这n-1级台阶就有climbStairs(n-1)种方法爬到楼梯顶；如果第一次往上爬2级台阶，就会剩下n-2级台阶，这n-2级台阶就有climbStairs(n-2)种方法爬到楼梯顶。所以有：climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)。显然，climbStairs(1)=1，climbStairs(2)=2。
用递归就能轻松描述以上信息：
int climbStairs(int n) {if (n <= 2){return n;}// f(n) = f(n-1) + f(n-2)return climbStairs(n-1) + climbStairs(n-2);
}
不过这样是过不了的，因为递归中存在大量重复的计算。
循环
一种简单的方法是把递归改成循环。由climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)可知，climbStairs(n)就是以1，2为前两项的斐波那契数列，从第三项开始，每一项都是前两项之和，所以只需要一项一项往后求就行了。
int climbStairs(int n) {if (n <= 2){return n;}int a = 1;int b = 2;int c = 0;// 第3项会进一次循环while (n-- > 2){c = a + b;a = b;b = c;}return c;
}
其他思路
当然，我们也有一些其他思路。比如，可以使用矩阵构建一个递推关系，如：
从而得到：
从而把问题转换成计算矩阵的幂的问题。
或者，直接使用特征根法计算出以上斐波那契数列的通项公式，即：
从而直接使用通项公式求解。
总结
爬楼梯问题本质上就是斐波那契数列问题。
感谢大家的阅读！
