Fibonacci Numbers Using Dynamic Programming

 The following code illustrates the implementation of Fibonacci Numbers using the Dynamic Programming concept. Here we have used two basic principles of DP that is optimal substructure and overlapping behaviour to solve the problem. 

The time complexity of problem is O(n2) and space complexity is O(n) as we are using a 1-d Array.

//Fibonacci Series using Dynamic Programming 

#include<stdio.h> 

int fib(int n) 

{

/* Declare an array to store Fibonacci numbers. */

int f[n+2]; // 1 extra to handle case, n = 0 

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

} 

int main () 

{ 

int n = 9; 

printf("%d", fib(n)); 

getchar(); 

return 0; 

}