Encyclopedia > Dynamic programming

  Article Content

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:

Algorithms that use dynamic programming

External links:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Dynamic programming

... 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 th ...