What is Dynamic Programming?

Software Development
#1

Dynamic Programming is one of the different algorithm paradigm. In this approach, the problems can be divided into some sub-problems and it stores the output of some previous subproblems to use them in future. It helps to reduce the computational time for the task.

There are two types of the Dynamic Programming Technique −

  • Overlapping Subproblem
  • Optimal Substructure

It is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

The following are the steps that the dynamic programming follows:

  • It breaks down the complex problem into simpler subproblems.
  • It finds the optimal solution to these sub-problems.
  • It stores the results of subproblems (memoization). The process of storing the results of subproblems is known as memorization.
  • It reuses them so that same sub-problem is calculated more than once.
  • Finally, calculate the result of the complex problem.
    The above five steps are the basic steps for dynamic programming. The dynamic programming is applicable that are having properties such as:

Let’s understand dynamic programming through an example.

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

In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of ‘n’ increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2n.