#### Dynamic Programming

**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 **n ^{th}** 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

**n**term of the series.

^{th}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.