ダイナミックプログラミングを使用したフィボナッチシリーズ

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

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 

をこのコードでは、再帰的に実行され、読みやすいです。配列などを初期化する必要はありません。

代わりにあなたが非再帰オプションを使用することができます：あなたはあなたの結果を保存したい場合は、あなたがあなたのFIB機能の外に配列を初期化する必要が

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; 
} 

を：

// 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)); 
    } 
}