用動態規劃演算法計算費波南西數列

動態規劃比遞迴寫法快好多.

public static void main(String[] args){
 long start = System.currentTimeMillis();
 System.out.println(new Fib().calFib(40));
 long end = System.currentTimeMillis();
 System.out.println("Dynamic Programming :" + (end - start) +" million seconds");
 start = System.currentTimeMillis();
 System.out.println(new Fib().recurFib(40));
 end = System.currentTimeMillis();
 System.out.println("Recurrence :" + (float)(end - start) +" million seconds");
 
    }
    
    int calFib(int toNumber){
  int[] value = new int[100];
  value[1] = 1;
  for(int i = 1; i <= toNumber ; i++){
      value[i+1] = value[i] + value[i-1];
  }
  return value[toNumber];
    }
    
    int recurFib(int toNumber){
 if(toNumber == 0){
     return 0;
 }else if(toNumber == 1){
     return 1;
 }else{
     toNumber -= 1;
     return recurFib(toNumber)+recurFib(toNumber-1);
 }
    }