##
**Dynamic Programming: **

Dynamic Programming is a method
for solving a complex problem by breaking it down into a collection of simpler
subproblems, solving each of those subproblems just once, and storing their
solutions using a memory-based data structure (array, map,etc). Each of the
subproblem solutions is indexed in some way, typically based on the values of
its input parameters, so as to facilitate its lookup. So the next time the same
subproblem occurs, instead of recomputing its solution, one simply looks up the
previously computed solution, thereby saving computation time. This technique
of storing solutions to subproblems instead of recomputing them is called
memoization.

Technique is among the most
powerful for designing algorithms for optimization problems. Dynamic
programming problems are typically optimization problems (find the minimum or
maximum cost solution, subject to various constraints). The technique is
related to divide-and-conquer, in the sense that it breaks problems down into
smaller problems that it solves recursively. However, because of the somewhat
different nature of dynamic programming problems, standard divide-and-conquer
solutions are not usually efficient. The basic elements that characterize a
dynamic programming algorithm are:

·

**Substructure:**
Decompose your problem into smaller (and hopefully simpler) subproblems.
Express the solution of the original problem in terms of solutions for smaller
problems.

·

**Table-structure:**
Store the answers to the sub-problems in a table. This is done because
subproblem solutions are reused many times.

·

**Bottom-up computation:**
Combine
solutions on smaller subproblems to solve larger subproblems. (We also discuss
a top-down alternative, called memorization)

The most important question in designing a DP solution to a
problem is how to set up the subproblem structure. This is called the
formulation of the problem. Dynamic programming is not applicable to all
optimization problems. There are two important elements that a problem must
have in order for DP to be applicable.

**Optimal substructure**:

(Sometimes called the principle of
optimality.) It states that for the global problem to be solved optimally, each
subproblem should be solved optimally. (Not all optimization problems satisfy
this. Sometimes it is better to lose a little on one subproblem in order to
make a big gain on another.)

**Polynomially many subproblems:**

An important aspect to the
efficiency of DP is that the total number of subproblems to be solved should be
at most a polynomial number.

## 0 Comments

Subscribe Us and Thanks for visiting blog.