The term Dynamic programming originally only applied to solving certain kinds of operational problems, quite outside the area of Computer Science, just as Linear programming did. In this context it has no particular connection to programming at all, and there is a mere coincidence of naming.
In the context of programming, Dynamic programming is an important technique which belongs to the theory of optimization.
Dynamic programming is efficient in finding optimal solution for cases with lots of overlapping subproblems. It solves problems by recombining solutions to subproblems, when the subproblems themselves may share subsubproblems. In order to avoid solving these subsubproblems several times, their results are gradually computed and memorized, starting from the simpler problems, until the overall problem itself is solved.
To apply dynamic programming for finding optimal solutions, the problem under concern must have optimal substructure. Optimal substructure means that the optimal solutions of local problems can lead to the optimal solution of the global problem.
In summary, dynamic programming makes use of:
Approaches Dynamic programming usually comes in two approaches:
Algorithms that use dynamic programming
External links:
Search Encyclopedia

Featured Article
