Dynamic programming is both a mathematical optimization method and an algorithmic paradigm that solves complex problems by breaking them into simpler, overlapping sub-problems and solving each just once, typically storing results to avoid recomputation. It applies to problems with optimal substructure, where an optimal solution can be built from optimal solutions of its sub-problems, formalized via the Bellman equation. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Disputed
Core PrincipleProblems exhibiting optimal substructure and overlapping sub-problems can be solved efficiently by recursive decomposition combined with caching of intermediate results, developed by Richard Bellman in the 1950s. 1 Bellman's own account of why he chose the name dynamic programming is contested: Russell and Norvig note his story cannot be strictly true, since his first paper using the term (1952) predates the political circumstances he described, and Harold Kushner has suggested other motives, such as wanting to distinguish the work from Dantzig's linear programming. Connections
In Field
Source Wikipedia: Dynamic Programming
Sources
1. Wikipedia: Dynamic Programming
Wikimedia FoundationOverview, Mathematical optimization section
Dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time.
Overview, History of the name
The term dynamic programming 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.
Overview, Bellman's first paper
his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953
- In Field: Algorithms and Complexity Theory
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.