Dynamic programming is a method for designing an algorithm to solve an optimization theory problem by decomposing it into overlapping subproblems and storing their solutions. The optimal value at one state is expressed recursively in terms of the values of states reachable from it, so each subproblem need be solved only once.

For a finite-horizon problem, the terminal values are specified first and backward induction evaluates the remaining states in reverse order using the same optimality relation recursively.

See also

Algorithm, Backward Induction, Held-Karp Algorithm, Optimization Theory, Recursion, Work Function Algorithm

Explore with Wolfram|Alpha

References

Bellman, R. E. Dynamic Programming. Princeton, NJ: Princeton University Press, 1957.

Cite this as:

Weisstein, Eric W. "Dynamic Programming." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DynamicProgramming.html

Subject classifications