liveBook · Manning

Dynamic programming

As explained in Timeless Algorithms, The Foundational Ideas

Dynamic programming is an algorithmic technique that solves problems by decomposing them into related subproblems and combining their solutions, often reusing computed results.

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

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Develops structural conditions, state design, recurrences, base cases, memoization, and tabulation, including the computational cost of additional state dimensions.
Examples
Uses Fibonacci recursion, knapsack, coin change, inventory planning, and least-cost routing to illustrate different formulations.
What it assumes
Introduces overlapping subproblems and optimal substructure as conditions to check before applying the method.
What you can do after
Apply it by defining states, transitions, recurrences, and base cases, then evaluating subproblems through memoization or tabulation.
How it connects
Connects dynamic programming to optimal substructure, Markov decision processes, reinforcement learning, and linear programming.

Also explained in

Compare how 8 books explain dynamic programming →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.