introduction to dynamic programming

dynamic programming is nothing but dividing a problem into small problems and storing the values of the small problems to calculate the overall problem.in this idea we reuse the data which is stored instead of calculating it again.
complex problems can be solved easily and time complexity is also reduced.

consider the example of calculating nth fibonacci number:

fib(n) = fib(n-1) + fib(n-2), where n >= 2.
 fib(0) = 0
 fib(1) = 1

the recursive solution of the above is:

int fib(int n) 
{ 
    if (n <= 1) 
        return n; 

    return fib(n-1) + fib(n-2); 
}



lets take a example : n=4

                  fib(4)                                                      

                /           \                                          

          fib(3)          fib(2)        

        /        \             /        \                   

    fib(2)   fib(1)    fib(1) fib(0)   

     /    \

fib(1) fib(0)

as u can c fib(2),fib(1),fib(0) are calculated more times , if n was larger than we had to repeat the process many times the time complexity is exponential,instead we can use dynamic programming


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

here we are reusing the previously stored value

the time complexity of the above dynamic approach is linear