跳台阶

阅读文本大概需要 3.2 分钟。

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路

1.在解决这个问题之前，我先抛出一个问题，假设有 10 级台阶，如果你只差一步就能走到第 10 级台阶上，那么此时你处于第几级台阶上。

2.我假设你已经经过思考得出是第 9 级台阶或者第 8 级台阶上了。

3.如果我们不考虑从 0 走到第 8 级的过程，也不考虑从 0 走到第 9 级的过程，要想走到第 10 级，最后一步必然是从第 8 级或者第 9 级开始。

4.假设从 0 级到第 8 级有 a 种走法，从 0 级到第 9 级有 b 种走法，那么从 0 级到第 10 级的走法就是 a+b。

5.由以上的思想我们可以得出一个结论，那就是

6.用公式来表示就是 f(10)=f(9)+f(8)。

7.那如何计算 f(9) 和 f(8) 呢,我相信你已经有答案了。

有了上面的思路，我相信你很快能写出这一份代码。

8.但是这份代码的时间复杂度爆炸，递归虽然好用，但是如果追求效率的话，递归就可以直接 pass 掉了。

9.可以想象一下当只有 3 级台阶的时候，计算的公式就是

10.从上面的状态转移方程中发现，f(1) 被计算了三次。如何不让 f(1) 重复计算呢？

11.很简单，用变量保存即可。使用递归的方式是自顶向下的计算方式，如果思维可逆，我们可以考虑使用自底向上的计算方式，因为我们很快的就能得到 f(1)=1,f(2)=2,采用迭代的方式，用三个变量保存状态转移方程中的 f(n),f(n-1),f(n-2)。

12.这种方式时间复杂度只有 O(n),空间复杂度只有 O(1),采用这种方式计算的思维，就是我们编程界大名鼎鼎的「动态规划」，下面看代码。

项目源码

如果你想看到《剑指offer》的所有源码，欢迎 star 我的 github project。

《剑指offer》的 github 地址：

https://github.com/liuenci/GoOffer