Dynamic Programming
Also known as: DP, Bellman's Principle of Optimality, Recursive Optimization, Dinamik Programlama
Dynamic Programming (DP) is an exact optimization technique introduced by Richard Bellman in 1957 for solving multi-stage decision problems. It decomposes a complex problem into simpler, overlapping subproblems, solves each subproblem once, and stores the results to avoid redundant computation. Grounded in the Principle of Optimality, DP guarantees globally optimal solutions whenever the problem exhibits overlapping subproblems and optimal substructure.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+5 more
When to use it
Dynamic Programming is appropriate when a problem has overlapping subproblems and optimal substructure — properties common in sequential decision-making, resource allocation, scheduling, and string alignment tasks. It requires that the state space be fully enumerable and of manageable size; the method suffers from the curse of dimensionality when state variables are many or continuous. For problems with intractable state spaces, approximate DP or reinforcement learning are preferable alternatives.
Strengths & limitations
- Guarantees exact globally optimal solutions for problems satisfying the Principle of Optimality.
- Eliminates redundant computation via memoization, achieving polynomial time in the number of states.
- Produces an explicit optimal policy, not merely an optimal value, enabling straightforward decision support.
- Broadly applicable across domains including control theory, bioinformatics, economics, and operations research.
- Suffers from the curse of dimensionality: memory and time requirements grow exponentially with the number of state variables.
- Requires complete prior knowledge of the transition structure and reward function; inapplicable to unknown environments without approximation.
- The state space must be discrete or discretizable; continuous high-dimensional problems demand approximation schemes that sacrifice exactness.
- Formulating the correct state representation and recurrence relation requires substantial problem-specific insight.
Frequently asked
What is the difference between dynamic programming and divide-and-conquer?
Both decompose problems into subproblems, but divide-and-conquer assumes independent subproblems solved only once naturally. Dynamic programming targets overlapping subproblems — the same subproblem appears in multiple branches — and memoizes results to avoid redundant work. Without overlapping subproblems, DP offers no computational advantage over straightforward recursion.
When should I use top-down memoization versus bottom-up tabulation?
Top-down memoization is easier to implement directly from the recurrence and computes only needed subproblems, benefiting sparse state spaces. Bottom-up tabulation avoids recursion overhead and stack limits, suits dense state spaces, and is often faster in practice. Choose top-down when the set of needed subproblems is hard to predict, bottom-up when all subproblems will be needed.
How does dynamic programming relate to reinforcement learning?
Classical DP requires a fully known Markov Decision Process model (transition probabilities and rewards). Reinforcement learning extends DP ideas to settings where the model is unknown, using sampled experience instead. Algorithms like Q-learning and policy gradient methods are approximate DP procedures that learn value functions from interaction rather than from an explicit model.
Sources
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. ISBN: 978-0-691-07951-6
How to cite this page
ScholarGate. (2026, June 2). Dynamic Programming. ScholarGate. https://scholargate.app/en/optimization/dynamic-programming
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Constraint ProgrammingOptimization↔ compare
- Deep Reinforcement LearningDeep learning↔ compare
- Integer ProgrammingOptimization↔ compare