Dynamic Programming is used to solve complex problems which exhibit the property of overlapping subproblems i.e a problem can be broken down into subproblems which are overlapping (subproblems are not independent or each subproblem may appear many times during the process of problem solving). It is a very efficient approach in which every subproblem is solved exactly once and the answer is saved in a table. The answers of each of the subproblem is then combined to get the final solution to the problem. It is based on look-up technique in which solution for a subproblem is retrieved from a table if it has been computed previously, else it is solved and the answer is saved in the table.
Consider the problem of finding the nth term of a fibonacci series. The recursive formulation of the problem is :
fib ( n ) = fib ( n – 1 ) + fib ( n – 2) where fib ( n ) gives the nth term of the series.
Now, fib ( 5 ) = fib ( 4 ) + fib ( 3 )
Here, the problem fib ( 5 ) is broken down into two subproblems fib ( 4 ) and fib ( 3 ). The subproblem fib ( 4 ) can be broken down into subsubproblems fib ( 3 ) and fib ( 2 ) . Observe that fib ( 3 ) is an overlapping subproblem. In a naive approach, each subproblem is solved as many times as it appears in the problem. In the dynamic programming approach, each subproblem is solved exactly once. In this case, fib ( 3 ) will be computed only once and this principle is valid for subsubproblems also.
Dynamic program is mainly used to solve optimization problems ( problems with many possible optimal solutions ). The first step is to determine the structure of an optimal solution and then construct the solution using that structure in a bottom-up manner.
Now, let’s put this theory into practice by solving some problems using dynamic programming technique.
Note : In a divide and conquer approach also, a problem is divided into subproblems but those are independent subproblems i.e each subproblem appears only once.