Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Concept

Dynamic Programming

Technique

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 Principle
Problems 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.
Origin Year
1952 1
FAQs

Why is it called dynamic programming?

The name does not mean computer programming: programming meant an optimal schedule and dynamic suggested time-varying.

Richard Bellman chose dynamic to capture the time-varying aspect of the problems, and because it sounded impressive. Programming referred to finding an optimal program in the sense of a military schedule for training or logistics, the same usage as in linear programming and mathematical programming. Bellman's own account says he picked the name to shield the Air Force from the word research. That story may be inaccurate: Russell and Norvig note it cannot be strictly true, because his first paper using the term appeared in 1952, before Wilson became Secretary of Defense in 1953.
Connections

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Dynamic Programming

Technique Used By

Baker's Technique, Algorithms
Bellman-Ford Algorithm, Algorithms
CYK Algorithm, Algorithms
Dynamic Time Warping Algorithm, Algorithms
Earley Parser, Algorithms
Floyd-Warshall Algorithm, Algorithms
Held-Karp Algorithm, Algorithms
Hirschberg's Algorithm, Algorithms
Image color transfer, Algorithms
Knuth-Plass Line-Breaking Algorithm, Algorithms
Levenshtein Distance Algorithm, Algorithms
Longest Common Subsequence Algorithm, Algorithms
LZMA Algorithm, Algorithms
Needleman-Wunsch Algorithm, Algorithms
Nussinov Algorithm, Algorithms
Otsu's Method Algorithm, Algorithms
Sequence Alignment, Algorithms
Shortest Common Supersequence, Algorithms
Smith-Waterman Algorithm, Algorithms
Uniform Cost Search Algorithm, Algorithms
Viterbi Algorithm, Algorithms
Warshall's Algorithm, Algorithms
Sources
1. Wikipedia: Dynamic Programming
Wikimedia Foundation
  • Overview, 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
  • In Group: Algorithm Design Strategies, Lead
    Dynamic programming (DP) is both a mathematical optimization method and an algorithmic paradigm.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.