数据结构与算法--fibonacci的动态规划解法

对比下面这个用一个数组来存储中间变量的方法：以下代码为JAVA：

1.    /** 
2.      * 自底向上包含"动态规划"思想的解法 
3.      * @param n 
4.      * @return 第n个斐波那契数 
5.      */  
6.     public static int downToTopReslove(int n) {  
7.         if(n == 0) {  
8.             return 0;  
9.         } else if(n == 1 || n == 2) {  
10.             return 1;  
11.         } else {  
12.             int[] fibonacciArray = new int[n+1]; //fibonacciArray[i]表示第i个斐波那契数  
13.             fibonacciArray[0] = 0;  
14.             fibonacciArray[1] = 1;  
15.             fibonacciArray[2] = 1;  
16.             for(int i=3;i<=n;i++) { //注意由于fibonacciArray[0]表示第0个元素，这里是i<=n，而不是i<n  
17.                 fibonacciArray[i] = fibonacciArray[i-1] + fibonacciArray[i-2];  
18.             }  
19.               
20.             return fibonacciArray[fibonacciArray.length-1];  
21.         }  
22.     }  

第一个算法只用了两个中间变量来存储中间值，每次值都会有变化，而第二个方法则是每个中间值都被存储在了对应的数组元素里。

上述两种算法都体现了动态规划的思想。