A locally cheap step need not lead to the cheapest route. Dynamic programming (DP) addresses such problems by breaking them into related subproblems, solving each distinct subproblem, and reusing its result. Richard Bellman developed the framework for multi-stage decision problems, where present choices affect the possibilities that remain. section 10.2.5 section 6.1
Two structural properties make this approach useful. Overlapping subproblems allow computed results to be reused. Optimal substructure means an optimal solution can be assembled from optimal solutions to its constituent subproblems. Without optimal substructure, the global optimality guarantee fails; without overlap, storing results offers little computational benefit. section 6.1.1 section 10.2.5
Figure 6.1 Recursive computation of the sixth Fibonacci number. Although the recursion tree branches rapidly, many intermediate values are computed repeatedly. These overlapping subproblems make the Fibonacci sequence an ideal candidate for dynamic programming, where each distinct subproblem is solved once and then reused whenever it reappears.

The Fibonacci recursion tree shows how repeated branches create opportunities to reuse computed values. section 6.1.1
A DP formulation specifies:
- States: the information needed to describe what remains at each stage. section 6.8
- Transitions and a recurrence: how choices lead to other states and how their results combine. section 6.8
- Base cases: known values that anchor the computation. section 6.8
For a deterministic least-cost route, the recurrence takes the form V(s) = minₐ [c(s, a) + V(s′)], with a specified value at the destination. Here V(s) is the best remaining cost from state s, c(s, a) is the immediate cost of choice a, and s′ is the state reached by that choice. The recurrence compares each immediate cost together with its downstream consequences. section 10.2.5
Memoization evaluates and caches states as needed; tabulation works iteratively from base cases. The choice depends on the structure and density of the state space. Both rely on a state representation that retains the information needed for correct decisions. section 6.8 section 10.2.5
Inventory planning
A retailer chooses an order quantity each period. The state records the period and available inventory; an order incurs an immediate cost and leads to a new inventory level after demand is satisfied. Working backward from a terminal cost or salvage value combines current costs with minimum future costs, rather than optimizing each period in isolation. section 6.4.2
The framework also handles counting: a coin-change recurrence can compute the number of valid combinations rather than an optimal selection. In constrained optimization, richer states can track several remaining budgets or resource limits, but each added dimension can greatly increase the number of subproblems. section 6.3.6 section 6.4.1
Under uncertainty, Markov decision processes use a Bellman equation to combine immediate reward with expected future value when transition probabilities and rewards are known. Reinforcement learning retains the recursive conception of value while using experience to supply information that classical model-based DP assumes is available. section 6.8 section 6.6.2







