--- title: "Dynamic programming" source: "https://systems-analysis.info/eng/Dynamic_programming" wiki: "systems-analysis.info/eng" article: "Dynamic_programming" language: "en" categories: - "Category:English" - "Category:Operations research" - "Category:Science" revision_id: 130 wiki_created_at: 2026-09-06T22:17:46Z wiki_modified_at: 2026-09-06T22:17:46Z downloaded_at: 2026-09-07T22:21:13Z --- # Dynamic programming **Dynamic programming** (**DP**) is a method for solving complex optimization problems by breaking them down into a sequence of simpler subproblems[\[1\]](https://systems-analysis.info/eng/Dynamic_programming#cite_note-en-wiki-dp-1). The method is applied to multi-stage decision-making processes, where the optimal solution to the entire problem can be constructed from the optimal solutions of its subproblems. The term was introduced by American mathematician Richard Bellman in the 1950s. In this context, the word "programming" refers to "planning" or "creating an optimal plan of action," rather than writing computer code[\[1\]](https://systems-analysis.info/eng/Dynamic_programming#cite_note-en-wiki-dp-1). ## Key Properties and Theorems The applicability of dynamic programming to a problem is determined by its possession of two fundamental properties. ### Bellman's Principle of Optimality The central concept of the method is **Bellman's principle of optimality**. It states: whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. In other words, any part of an optimal trajectory is itself optimal. This property allows the overall problem to be broken down into a sequence of simpler subproblems and solved recursively. ### Overlapping Subproblems A problem has the property of **overlapping subproblems** if its recursive solution involves solving the same subproblems multiple times. DP avoids re-computation by storing the solutions to subproblems that have already been encountered (a technique called memoization or tabulation), which significantly improves efficiency compared to a naive recursive search. ## The Bellman Equation The principle of optimality gives rise to the method's fundamental recurrence relation—the **Bellman equation**. It connects the "value" (optimal payoff or cost) of the current state with the values of subsequent states. In its general form for a deterministic multi-stage process with an additive objective function, it is written as: $$ V_{k - 1}(x) = \max\limits_{y \in U(x)}\{\varphi_{k}(x,y) + V_{k}(f_{k}(x,y))\} $$ where: - $k$ — step number (from $m$ to 1); - $x$ — state of the system at step $k - 1$; - $y$ — control decision made at step $k$; - $\varphi_{k}(x,y)$ — payoff (or cost) at step k; - $f_{k}(x,y)$ — function defining the new state of the system; - $V_{k}(s)$ — optimal value of the objective function for the subproblem starting at step $k$ in state $s$. The equation is solved sequentially, typically "backwards," moving from the last step to the first. ## Examples of Application - **Shortest path problem in a graph**: This problem exhibits optimal substructure, as any subpath of a shortest path is itself a shortest path. The Bellman-Ford and Floyd-Warshall algorithms are classic examples of applying DP to solve this problem[\[2\]](https://systems-analysis.info/eng/Dynamic_programming#cite_note-mit-amp-2). - **Knapsack problem**: The problem of optimally filling a knapsack of limited capacity with items of different values and weights. DP can solve this problem by considering items sequentially and, at each step, calculating the maximum value for all possible remaining capacities. - **Resource allocation problem**: The allocation of a limited resource (e.g., investments) among several projects to maximize the total return. ## Limitations The main limitation of the method is the **curse of dimensionality**, a term coined by Bellman to describe the exponential growth in the number of states—and consequently, the computational complexity—as the number of variables describing the system's state increases[\[3\]](https://systems-analysis.info/eng/Dynamic_programming#cite_note-utexas-ormm-3). This limits the practical application of exact DP for problems of very high dimensionality. ## Related Concepts - [Operations research](https://systems-analysis.info/eng/Operations_research "Operations research") - Optimal control theory - Markov decision process (stochastic generalization) - Hamilton–Jacobi–Bellman equation (continuous-time analog) ## See also - [Network model (operations research)](https://systems-analysis.info/eng/Network_model_(operations_research) "Network model (operations research)") - [Operations research models](https://systems-analysis.info/eng/Operations_research_models "Operations research models") - [Integer programming](https://systems-analysis.info/eng/Integer_programming "Integer programming") ## References 1. ↑ [1.0](https://systems-analysis.info/eng/Dynamic_programming#cite_ref-en-wiki-dp_1-0) [1.1](https://systems-analysis.info/eng/Dynamic_programming#cite_ref-en-wiki-dp_1-1) "Dynamic programming". *Wikipedia*. [1] 2. [↑](https://systems-analysis.info/eng/Dynamic_programming#cite_ref-mit-amp_2-0) Bradley S. P., Hax A. C., Magnanti T. L. (1977). *Applied Mathematical Programming*. Addison-Wesley. [2] 3. [↑](https://systems-analysis.info/eng/Dynamic_programming#cite_ref-utexas-ormm_3-0) Jensen P. A. (2004). *Dynamic Programming – Models*. Operations Research Models and Methods, Univ. of Texas. [3]