题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
解析
(1)递归方式
对于公式f(n) = f(n-1) + f(n-2)，明显就是一个递归调用，因此根据f(0) = 0和f(1) = 1我们不难写出如下代码：
public int Fibonacci(int n) {
if(n == 0 || n == 1){
return n;
}
return Fibonacci(n - 1) + Fibonacci(n - 2);
}存在问题
性能浪费，存在大量重复运算；n增大时，会产生栈溢出
（2）数组方式
public int fibonacci(int n){
int[] fibonacci=new int[n];
fibonacci[0]=0;
fibonacci[1]=1;
for(int i=2;i<n;i++)
fibonacci[i]=fibonacci[i-1]+fibonacci[i-2];
return fibonacci[n-1];
}运行次数减少，但是空间换时间，空间占用增大
（3）动态规划
动态规划就在使用递归调用自上而下分析过程中发现有很多重复计算的子过程，于是采用自下而上的方式将每个子状态缓存下来，这样对于上层而言只有当需要的子过程结果不在缓存中时才会计算一次，因此每个子过程都只会被计算一次。
public int Fibonacci(int n) {
int preNum=1;
int prePreNum=0;
int result=0;
if(n==0)
return 0;
if(n==1)
return 1;
for(int i=2;i<=n;i++){
result=preNum+prePreNum;
prePreNum=preNum;
preNum=result;
}
return result;
}（4）尾递归
什么是尾递归 ？
简单理解，就是处于函数尾部的递归调用本身的情形下，前面的变量状态都不需要再保存了，可以释放，从而节省很大的内存空间。在前面的代码中，明显在调用递归调用Fibonacci(n-1)的时候，还有Fibonacci(n-2)没有执行，需要保存前面的状态，因此开销较大的。
public int result(int n) {
return Fibonacci2(n,0, 1);
}
int Fibonacci2(int n, int a, int b) {
if (n==0) return a;
else {
return Fibonacci2(n-1, b, a+b);
}
}派生
（1）青蛙跳台阶（每次跳1或2个台阶）
思路：跳n个台阶的第一步只能有两种跳法，1阶或2阶梯，第一次1，后面的跳法和n-1个台阶的一样多f(n-1)，跳2的，后面有f(n-2)个跳法；所以有f(n) = f(n-1)+f(n-2)
（2）变态青蛙跳台阶（每次跳1、2、3、、、、n个台阶）
思路和青蛙跳台阶相似；结论为f(n) = f(n-1)+f(n-2)+f(n-3)+...+f(n-n);
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1),(n>=2)
public int JumpFloorII(int target) {
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}优化，可直接用乘方运算或位运算代替递归
（3）矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：有了之前的历练，我们能很快的写出递归版本：先竖着放一个或者先横着放两个，剩下的交给递归处理