Серия Фибоначчи с использованием динамического программирования

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

Если вы хотите сохранить ваши результаты, вы должны инициализировать массив за пределами вашей функции выдумки:

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