Dynamic Programming - Overlapping subprobelm paradigm

/* Dynamic programming explained using a simple Fibonacci numbers
* 1- Overlapping subproblem type 
*  Recrusive style 
*/

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


}

Recursion tree for fib(5) -

Notice  that the fib(3) is being calculated two times
And many more are subproblem recalcualtion is present too .
So if we can save the result of subproblems, then the overlapped subproblems
can be solved efficiently .

Two ways -
1 - Memoization - top down
2 - Tabulationn - bottom up


//Memoizazed Fibonacci numbers evaluation 



#include<stdio.h>
#define NIL -1 
#define MAX 100 

int lookup[MAX];

// function to initialize the look up table 
void _intialize()
{
int i;
for (i = 0; i < MAX; ++i)
lookup[i] = NIL;

}



int fib(int n)
{
if (lookup[n] == NIL)
{
if (n <= 1)
lookup[n] = n; 
else
lookup[n] = fib(n - 1) + fib(n - 2); 

}

return lookup[n];


}



 //driver main function
int main()
{
int n = 40; 
_intialize();
printf("the  40th  Fibbonacci number  %d  ", fib(n)); 
getchar();
return 0; 
 

 }



Tabulated version of nth Fibbonacci numbers


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

return f[n];


}











//