Dynamic programming is a method for solving problems that can be broken into subproblems which overlap, meaning the same smaller problem arises again and again. Rather than recompute each one, a dynamic programming solution computes every distinct subproblem just once and stores its answer, then builds the final result from those stored pieces. This trades extra memory for a large saving in time.
The term was coined by Richard Bellman at the RAND Corporation in the 1950s. In his 1954 paper “The Theory of Dynamic Programming,” published in the Bulletin of the American Mathematical Society, Bellman set out the mathematical framework for treating a sequence of decisions as a whole and analyzing it through what he called functional equations.
Central to Bellman’s framework is the principle of optimality: an optimal sequence of decisions has the property that, whatever the first decision is, the remaining decisions must themselves form an optimal sequence with respect to the situation that the first decision produced. This is what lets a large optimization problem be solved by combining the optimal solutions of its smaller parts.
The technique underlies many classic algorithms, including shortest-path methods such as Bellman-Ford, and is presented in the MIT 6.006 “Introduction to Algorithms” lecture notes as a systematic way to define subproblems, relate them, and order their computation. Dynamic programming differs from plain divide and conquer precisely because its subproblems overlap, which is what makes storing and reusing their answers worthwhile.