The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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