原本以为比较简单，但是后来发现，加能使用动态规划，算法更好。

1.题目

　　大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。

 

2.分析递归方法

1  public int fib0(int n)2     {3         if(n<=0)4             return 0;5         if(n==1)6             return 1;7         return fib( n-1)+fib(n-2);8     }

　假设输入的是6：

　

　　

　　上面的递归树中的每一个子节点都会执行一次，很多重复的节点被执行，fib(2)被重复执行了5次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。下面就看看动态规划的两种方法怎样来解决斐波拉契数列Fibonacci 数列问题。

3.使用动态规划

　　①自顶向下的备忘录法

1 public static int Fibonacci(int n) 2     { 3         if(n<=0) 4             return n; 5         int [] Memo=new int[n+1]; 6         for(int i=0;i<=n;i++) 7             Memo[i]=-1; 8         return fib(n, Memo); 9     }10     public static int fib(int n,int []Memo)11     {12         if(Memo[n]!=-1)13             return Memo[n];14         //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。15         if(n<=2)16             Memo[n]=1;17         else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);18         return Memo[n];19     }

　　备忘录法也是比较好理解的，创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib（n）的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在Memo数组中，下次在调用fib（n）的时候就不会重新递归了。比如上面的递归树中在计算fib（6）的时候先计算fib（5），调用fib（5）算出了fib（4）后，fib（6）再调用fib（4）就不会在递归fib（4）的子树了，因为fib（4）的值已经保存在Memo[4]中。

 

　　②自底向上的动态规划

　　备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

1 public static int fib(int n) 2     { 3         if(n<=0) 4             return n; 5         int []Memo=new int[n+1]; 6         Memo[0]=0; 7         Memo[1]=1; 8         for(int i=2;i<=n;i++) 9         {10             Memo[i]=Memo[i-1]+Memo[i-2];11         }12         return Memo[n];13     }

　　③优化

　　自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。观察参与循环的只有 i，i-1 , i-2三项，因此该方法的空间可以进一步的压缩如下。

1 public static int fib3(int n) 2     { 3         if(n<=1) 4             return n; 5  6         int Memo_i_2=0; 7         int Memo_i_1=1; 8         int Memo_i=1; 9         for(int i=2;i<=n;i++)10         {11             Memo_i=Memo_i_2+Memo_i_1;12             Memo_i_2=Memo_i_1;13             Memo_i_1=Memo_i;14         }15         return Memo_i;16     }

 

4.完整的程序

1 package first; 2  3 public class Fibonacci { 4     public static void main(String[] args){ 5         // 6         int a=Fibonacci(3); 7         System.out.println("a="+a); 8         // 9         int b=fib(3);10         System.out.println("b="+b);11     }12 13     public int fib0(int n)14     {15         if(n<=0)16             return 0;17         if(n==1)18             return 1;19         return fib( n-1)+fib(n-2);20     }21 22 23     public static int Fibonacci(int n)24     {25         if(n<=0)26             return n;27         int [] Memo=new int[n+1];28         for(int i=0;i<=n;i++)29             Memo[i]=-1;30         return fib(n, Memo);31     }32     public static int fib(int n,int []Memo)33     {34         if(Memo[n]!=-1)35             return Memo[n];36         //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。37         if(n<=2)38             Memo[n]=1;39         else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);40         return Memo[n];41     }42 43     public static int fib(int n)44     {45         if(n<=0)46             return n;47         int []Memo=new int[n+1];48         Memo[0]=0;49         Memo[1]=1;50         for(int i=2;i<=n;i++)51         {52             Memo[i]=Memo[i-1]+Memo[i-2];53         }54         return Memo[n];55     }56 57     public static int fib3(int n)58     {59         if(n<=1)60             return n;61 62         int Memo_i_2=0;63         int Memo_i_1=1;64         int Memo_i=1;65         for(int i=2;i<=n;i++)66         {67             Memo_i=Memo_i_2+Memo_i_1;68             Memo_i_2=Memo_i_1;69             Memo_i_1=Memo_i;70         }71         return Memo_i;72     }73 74 75 76 }