##  [Dynamic Programming](/dynamic-programming-2) 

 Definition

A recursive optimization method for multi‑stage decision problems that decomposes a problem into overlapping subproblems, uses a state representation and the principle of optimality to express the value of a state as a function of successor states, and computes optimal policies by value or policy iteration, memoization, or backward induction.

 

 

 

 

 

 





## Principle

Principle

An optimal solution to a multi‑stage problem can be constructed from optimal solutions of its subproblems (principle of optimality); therefore computing a value function on a suitably defined state space yields globally optimal decisions when stagewise separability and the Markov property hold.

 

 

 

 

 





## Demonstration

Demonstration

Illustrative scenario: shortest‑time routing on a directed acyclic network. Situation: each node represents a stage, edge weights are stage costs. Recognition: costs satisfy stagewise additivity and future costs depend only on the current node. Action: compute minimal cost to destination for all nodes by backward induction (memoize results). Consequence: the computed policy gives the shortest path from every start node without enumerating all complete routes.

 

 

 

 

## Misapplication

Misapplication

Treating problems as amenable to dynamic programming when the chosen state does not encode all relevant history (violating the Markov property) or when subproblems are not overlapping; this can produce incorrect decisions or cause exponential state growth that negates computational benefits.

 

 

 

 

 





## Consequence

Consequence

When applicable, dynamic programming produces provably optimal policies and often reduces repeated computation via memoization; when misapplied it yields incorrect optima or infeasible computation due to the curse of dimensionality.

 

 

 

 

## Reversal

Reversal

If stagewise separability, additivity of costs, or the Markov property does not hold (for example, when future costs depend on full past trajectories or nonseparable objectives exist), the method must be replaced or augmented by reformulation, approximation, or history‑dependent state expansion.

 

 

 

 

 





## Boundary

Boundary

Clearly within: finite‑horizon Markov decision problems with additive stage costs and well‑defined states. Boundary case: stochastic problems with partial observability — can require belief‑state transformation. Clearly outside: single‑stage optimization without sequential structure or problems whose optimum depends on unbounded past history.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Optimality versus tractability — achieving exact global optimality via exhaustive state enumeration conflicts with limits on memory and computation, often forcing approximate or heuristic alternatives.

 

 

 

 

 





## Synthesis

Synthesis

Dynamic programming is a method of trading problem structure (stage decomposition and a compact state definition) for solvability: success depends primarily on choosing a state representation that makes future costs Markovian while keeping the state space tractable.