斐波那契数列

　　斐波那契数列满足如下定义：

　　　　当n=0时，f(0)=0;

　　　　当n=1时，f(1)=1;

　　　　当n>1时，f(n)=f(n-1)+f(n-2);

　　可以很快写出类似如下的代码：

1 public static long f(int n){
2         if(n < 0) return -1;
3         if(n == 0) return 0;
4         if(n == 1) return 1;
5         return f(n - 1) + f(n - 2);
6     }

　　但是如上递归解法有很严重的效率问题，例如计算f(10)的值，需要f(8)和f(9)的和，子递归一f(8)需要计算f(6)和f(7)的和，子递归二中计算f(9)的值需要f(8)和f(7)的和，此时f(8)又重复算了一次。此算法的时间复杂度是以n的指数的方式递增的。

　　改进的方法可以考虑从f(0)逐步计算到f(n)（即先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……），并用一个长度为2的整型数组存储每次需要迭代的值。很明显，此算法的时间复杂度值有O(n)。

 1 public static long f(int n){
 2         if(n < 0) return -1;
 3         long[] arr = {0, 1};
 4         if(n < 2) return arr[n];
 5         long pSum;
 6         for(int i = 2; i <= n; i++){
 7             pSum = arr[0] + arr[1];
 8             arr[0] = arr[1];
 9             arr[1] = pSum;
10         }
11         return arr[1];
12     }

　　接下来来看一下斐波那契数列的应用

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

　　先从最简单情况出发：

　　　　如果有1级台阶，则只有一种跳法，即f(1)=1。

　　　　如果有2级台阶，则可以有两种跳法（1级1级跳或2级跳），即f(2)=2。

　　　　如果有3级台阶，考虑第一次跳的时候有两种选择：一种是一次跳1级，则此跳法数目等于剩下（3-1）级台阶的跳法，即等于f(3-1)，另一种是一次跳2级，则此跳法数目等于剩下的（3-2）级台阶的跳法，即等于f(3-2)，所以f(3)=f(3-1)+f(3-2)=3。

　　再从一般情况出发：

　　　当n>2时，第一次跳有两种选择：一种是一次跳1级，则跳法数目等于后面剩下（n-1）级台阶的跳法，即f(n-1)，一种是一次跳2级，则跳法数目等于后面剩下的（n-2）级台阶的跳法，即f(n-2)，所以f(n)=f(n-1)+f(n-2)。

　　不难看出这实际上就是斐波那契数列了。