算法：斐波那契数列，青蛙跳台阶

数据结构和算法

写出一个函数，输入n，求斐波那契数列的第n项，定义如下：Fibonacci number, 其中有f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)(n>1)

避免重复计算

1. 可以将数组得到的中间项保存下来，下次需要时先查找一下，如果已经存在就不用再计算了，也可以用hash
2. 更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)，时间复杂度为O(n)
   

还可以有时间复杂度为O(logn)的解法

矩阵相关的

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

f(1)=1
f(2)=2
f(3)=f(1)+f(2)...
f(n)=f(n-1)+f(n-2)