Dynamic Programming optimizations for fibonacci series

 

• the sum of preceding two number.

for example, f(n) = { 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , ……………..}

mathematical function: f(n) = f(n-1) + f(n-2) , where n>=2 and f(0) = 0 , f(1) = 1

• Sample program:

/* simple recursive program for Fibonacci series */

int fibonacci(int n)

{

if (n<=1)

return n;

return fibonacci(n-1)+fibonacci(n-2);

}

• Overlapping problem:

In the above tree diagram we can see (for underlined subtrees) that the left subtree of fib(5) and right subtree of fib(4) are repeated likewise other subtrees are also repeated , to avoid this we use dynamic programming (here Memoization technique particularly).

• Optimized function code to reduce time complexity:

int fibonacci(int n)

{

if (table [n] == -1)

{

if (n<=1)

table [n] = n;

else

table [n] = fibonacci(n-1)+fibonacci(n-2);

}

return table [n];

}

In above problem we created a lookup table to save values which are calculated first and use them again if required rather than recalculating it, it will reduce much time for execution of a code .

Time required for calculating fibonacci(40):

1. Recursive function: approx 14 secs.
2. Using Memoization technique: approx 0.17 secs.