使用動態規劃的斐波那契數列

Question

讓我們考慮使用動態規劃實現斐波那契數列。

// Fibonacci Series using Dynamic Programming 
class fibonacci 
{ 
static int fib(int n) 
{ 
    /* Declare an array to store Fibonacci numbers. */ 
int f[] = new int[n+1]; 
int i; 

/* 0th and 1st number of the series are 0 and 1*/ 
f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    /* Add the previous 2 numbers in the series 
    and store it */ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
} 

public static void main (String args[]) 
{ 
    int n = 9; 
    System.out.println(fib(n)); 
} 
} 

我們使用動態編程，以便不會發生遞歸工作的重複。但是，在每次調用該函數時，都會生成一個新數組。那麼這個算法怎麼會被說成是更優化的呢？

Answer 1

一個優化只會保存最後2個值而不是所有結果。您不需要存儲所有結果。

您還可以在O（n）的遞歸編寫斐波納契數列：

int fib(int n1, int n2, int counter) 
{ 
    if(counter == 0) 
    { 
     return n2; 
    } 
    else 
    { 
     return fib(n2,n2 + n1,counter-1); 
    } 
} 

//to start: 
int result = fib(0,1,100); //gives you the 100 fibonacci value 

此代碼遞歸運行，易於閱讀。您不必初始化數組或其他東西。

或者你可以使用非遞歸選項：如果你想存儲你的結果

int fib(int number) 
{ 
    int n1 = 0; 
    int n2 = 1; 
    int temp; 
    for(int i = 0; i< number;i++) 
    { 
     temp = n1 + n2; 
     n1 = n2; 
     n2 = temp; 
    } 
    return n2; 
} 

，您必須將數組初始化FIB功能之外：

// Fibonacci Series using Dynamic Programming 
class fibonacci 
{ 
    /* Declare an array to store Fibonacci numbers. */ 
    int f[]; 

    static void init(int n) 
    { /* 0th and 1st number of the series are 0 and 1*/ 
     f = new int[n+1];    
     f[0] = 0; 
     f[1] = 1; 
    } 

    static int fib(int n) 
    { 
     int i; 

     for (i = 2; i <= n; i++) 
     { 
      /* Add the previous 2 numbers in the series 
      and store it */ 
      f[i] = f[i-1] + f[i-2]; 
     } 

     return f[n]; 
    } 

    public static void main (String args[]) 
    { 
     int n = 9; 
     init(n); 
     System.out.println(fib(n)); 
    } 
}