Dynamic Programming-2

In continuation to Dynamic Programming,let us discuss a simple problem.

Fibonacci Series:

A series of numbers in which each number is the sum of the two preceding numbers.
Fibonacci sequence is widely used for better understanding of DP.
Let us consider a general method to find the nth member of the fibonacci series.

General Recursive method of Fibonacci:

fib(int n)
{
 if(n==0)
 return 0;
 else if(n==1)
 return 1;
 else
 return (fib(n-1)+fib(n-2));
}

             

Consider the following recursive calls for n=5.

 
Time complexity is T(n)=T(n-1)+T(n-2) i.e, Exponential



Here,we are calculating fib(2) for 3 times.This is called overlapping of sub problems.
The moment when we start recomputing the solved problems the time will increases unnecessarily .To avoid such overhead we can go for dynamic programming.

Using DP:

The idea is to maintain an array for storing the computed results.
we first initialize res[0]=0,res[1]=1 .when we want to find the next item we simply add the before two results.

Here is the implementation:

int fib(int n)
{
 int res[n+1];
 int i;
 res[0]=0;
 res[1]=1;
 for(i=2;i<=n;i++)
{
 res[i]=res[i-1]+res[i-2];
 }
return res[n];
}

Time Complexity is O(n)
Space Complexity is O(n)
                                   
In this implementation,we are not simply computing the results,instead we are storing the results,so that they can be used in the future computations.As a result we can greatly reduce the time complexity.