Introduction
A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states.DP applies when the subproblems overlap - that is, when subproblems share subsubproblems.
A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value.
When developing a dynamic-programming algorithm, we follow a sequence of four steps:
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from computed information.
http://en.wikipedia.org/wiki/Dynamic_programming
