开始学算法（刷算法题）过程记录 9

题目描述：斐波那契数列

题目实现：

用递归的方法解决：

传个10进去，我们可以画出这样的调用图

可以看到f(7)被调用了3次，f(6)被调用了3次等重复计算情况。重复节点的数量会随着n的增大而急剧增加

更简单的方法是从下往上计算

把结果摆出来可以发现大于2之后每一项都是前2项之和

书中代码是这样的

这个代码还可以简化成下面这样：

相关题目1：一个青蛙可以跳上一级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法。

解题思路：画图比较好理解，如下图

聪明的小伙伴应该看出来就是：1,1,2,3,5 斐波那契数列了。

我们可以换个角度看：那就是青蛙已经在第三层了，那他要不是从第2层跳上来的，要不就是从第一层跳上来的。

那他有几种方法跳到第二层呢 有2种 有几种方法跳到第一层 有1种 。 所以第三层跳法是1+2=3种。

或者我们看他在第二层的时候，要不是从0层跳上来的，要不就是从1层跳上来的。这时候第一层的跳法是可以复用的，

在第三层的时候，可以复用第一层的跳法结果和第二层的跳法结果。

所以设n为层数，第n层的跳法数目等于第n-1层的跳法数目加上n-2层的跳法数目。

也就是：f(n)=f(n-1)+f(n-2)。算法实现和上题一样。

本题扩展：条件改成：一次可以跳n级，此时跳上一个n级台阶总共有多少种跳法，书中给了公式f(n)=2^n-1 。也就是后一个是前一个的2倍。

算法实现：