Dynamic programming (DP) is a general approach in making a sequence of interrelated
decisions to obtain an optimal solution. We can describe the general characteristics, but
the details depend on the application. Fundamentally, DP is recursive, like a computer
routine that calls itself, adding information to a stack each time, until certain stopping
conditions are met. Once stopped, the solution is unraveled by removing information
from the stack in the proper sequence.
Procedures of DP:
1. Define a small part of the whole problem and find an optimum solution to this small part.
2. Enlarge this small part slightly and find the optimal solution to the new problem based the previously found optimal solution.
3. Continue with Step 2 until you have enlarged sufficiently that the current problem encompasses the original problem. When this problem is solved, the stopping conditions will have been met.
4. Track back the solution to the whole problem from the optimal solutions to the
small problems solved along the way.