Dynamic programming

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 sub-subproblems. In order to avoid solving these sub-subproblems 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:

• Overlapping subproblem
• Optimal substructure

Approaches Dynamic programming usually comes in two approaches:

• Top-down Approach[?]
• Bottom-up Approach[?]

Algorithms that use dynamic programming

• the Cocke-Younger-Kasami (CYK) algorithm determines whether and how a given string can be generated by a given context-free grammar.

• The use of transposition tables and refutation tables[?] in computer chess

• the Viterbi algorithm

External links:

• http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch21