阅读文本大概需要 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
领取专属 10元无门槛券
私享最新 技术干货