Concepts

Dynamic Programming

Technique

Citation Formats

General Reference

Computing Atlas. "Dynamic Programming." Accessed August 30, 2026. https://dev-computing.interactiveatlas.org/concepts/dynamic-programming.

APA Style

Computing Atlas. (n.d.). Dynamic Programming. Retrieved August 30, 2026, from https://dev-computing.interactiveatlas.org/concepts/dynamic-programming

BibTeX

@misc{computingatlas-dynamic-programming,
  author = {Computing Atlas},
  title = {Dynamic Programming},
  year = {2026},
  url = {https://dev-computing.interactiveatlas.org/concepts/dynamic-programming},
  note = {Accessed August 30, 2026}
}

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.

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

Cross-Tradition Connections