Dynamic programming

From Wikiversity
(Redirected from Topic:Dynamic programming)
Jump to: navigation, search
Document spider web.svg This resource is currently unmaintained. Please feel welcome to adopt it and then change this tag.

In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure that takes much less time than naïve methods.

The term was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he had refined this to the modern meaning. The field was founded as a systems analysis and engineering topic which is recognized by the IEEE.

The word "programming" in "dynamic programming" has no particular connection to computer programming at all. A program is, instead, the plan for action that is produced. For instance, a finalized schedule of events at an exhibition is sometimes called a program. Programming, in this sense, is finding an acceptable plan of action.

Algorithms that use dynamic programming[edit]