liveBook · Manning

Chapter 6: Dynamic programming: Richard Bellman and recursive optimization

What you will learn in chapter 6 of Timeless Algorithms, The Foundational Ideas

The introduction frames dynamic programming as Bellman’s way to optimize interconnected decisions by reusing solutions to smaller problems.

After this chapter you will be able to

Section by section

Introduction

The introduction frames dynamic programming as Bellman’s way to optimize interconnected decisions by reusing solutions to smaller problems.

Key terms: dynamic programming, subproblems, recursive, globally optimal solution, underlying structure, problem formulation, smaller solutions

6.1 The dynamic programming paradigm

This section introduces dynamic programming as a way to make multistage problems manageable by formulating them as connected stages with reusable subproblem solutions, and places Bellman’s insight in its RAND setting.

Key terms: dynamic programming, stages, subproblems, problem formulation, partial solutions, Richard Bellman, RAND Corporation, resource allocation

6.1.1 Structural prerequisites for dynamic programming

This section explains the two structural conditions that determine whether dynamic programming is appropriate: overlapping subproblems and optimal substructure.

Key terms: overlapping subproblems, Fibonacci sequence, optimal substructure, globally optimal solution

6.1.2 Expressing problems as recurrence relations

This section explains how a recurrence relation serves as the mathematical blueprint for a dynamic programming solution.

Key terms: recurrence relation, smaller instances, subproblems, Fibonacci sequence

6.1.3 States, transitions, and base cases: the anatomy of a dynamic programming solution

This section explains how states, transitions, and base cases turn a recurrence into a dynamic programming formulation that can be evaluated systematically.

Key terms: state, subproblem, recurrence relation, transition, base case, recursive, iterative

6.1.4 Implementation methods

This section explains how tabulation and memoization evaluate the same dynamic programming recurrence in different orders and when each method is preferable.

Key terms: tabulation, bottom-up, memoization, top-down, base cases, table, state space, dense, sparse, dependency order

6.1.5 From principles to practice

This section emphasizes careful problem formulation in dynamic programming and contrasts its sequential structure with linear programming’s simultaneous treatment of variables.

Key terms: overlapping subproblems, optimal substructure, recurrence, state representation, transitions, base cases, dynamic programming, linear programming, multi-stage decision problems, sequential decisions

6.2 Constrained optimization: the knapsack problem

The section introduces 0/1 knapsack as a constrained optimization problem and explains why dynamic programming is useful for solving it.

Key terms: 0/1 knapsack problem, weight, value, carrying capacity, indivisible, greedy algorithm, brute-force enumeration, dynamic programming, subproblems, globally optimal solution

6.2.1 Verifying prerequisites

This section shows why the 0/1 knapsack problem meets the two structural prerequisites for dynamic programming.

Key terms: overlapping subproblems, state, 𝑉(𝑖, 𝑐), optimal substructure, remaining capacity

6.2.2 Specifying the recurrence

This section specifies the 0/1 knapsack recurrence and explains how its include-or-exclude decisions build an optimal value from smaller subproblems.

Key terms: 𝑉(𝑖, 𝑐), remaining capacity, recurrence relation, max operator, principle of optimality, smaller subproblems, globally optimal solution

6.2.3 Defining states, transitions, and base cases

This section defines the states, transitions, and base cases used to evaluate the 0/1 knapsack problem.

Key terms: two-dimensional state space, state, remaining capacity, V(i, c), transition, excluded, included, weight, base cases, boundaries of the state space

6.2.4 Choosing an implementation strategy

This section explains how to tabulate the 0/1 knapsack states and why tabulation is preferred over memoization for this problem.

Key terms: tabulation, V(i, c), base cases, recurrence relation, include-or-exclude decision, dense, state space, memoization

6.2.5 Solving the 0/1 knapsack problem

Works through a bottom-up table for a four-item 0/1 knapsack problem, showing how each row improves on earlier solutions and why the final value does not by itself identify the chosen items.

Key terms: tabulation, base cases, capacity, row, recurrence, excluding, including, remaining capacity, optimal value, 𝑉(4, 7)

6.2.6 Reconstructing the selected items

The section shows how to recover the items in an optimal knapsack solution by backtracking through the completed value table.

Key terms: backtracking, V(i, c), remaining capacity, forward tabulation

6.3 Counting solutions: the coin change problem

This section introduces coin change as a dynamic programming problem that counts distinct solutions rather than finding an optimal one.

Key terms: dynamic programming, enumeration problems, optimization problem, coin change problem, combinations, permutations, distinct combinations

6.3.1 Verifying the prerequisites

This subsection shows why the coin change counting problem has the two structural properties needed for dynamic programming.

Key terms: remaining amounts, dynamic programming, optimal substructure, counting

6.3.2 Specifying the recurrence

This section describes how coin-change counts build from smaller amounts and why the updates must avoid counting different orders of the same coins separately.

Key terms: ways[𝑛], denomination, distinct combinations, knapsack recurrence, combinations, permutations, updates

6.3.3 Defining states, transitions, and base cases

This section defines the states, count updates, and zero-amount base case for counting coin-change combinations.

Key terms: state, ways[n], transition, denomination, base case, ways[0], tabulation

6.3.4 Choosing an implementation strategy

This subsection explains how to tabulate coin-change counts so that each combination is counted once, regardless of coin order.

Key terms: tabulation, denomination, ways[𝑛], combinations, permutations

6.3.5 Solving the coin change problem

This section works through a coin-change table for amount 12, processing 1-, 5-, and 10-unit coins to count four distinct combinations.

Key terms: base case, ways[0], tabulation, denomination, combinations, ways[𝑛 – 5], ways[𝑛 – 10], ways[12]

6.3.6 Interpreting the solution

Interprets the coin-change count by listing all four combinations and contrasts counting solutions with optimizing a selection.

Key terms: ways[12], distinct combinations, denominations, knapsack problem, backtracking, tabulation, recurrence

6.4 Real-world applications of dynamic programming

This section contrasts compact dynamic programming examples with real-world applications that use the same framework under greater complexity.

Key terms: dynamic programming, states, transitions, decision horizons, state spaces

6.4.1 Constrained optimization

This section extends the knapsack approach to decisions with multiple resource constraints and explains the resulting computational tradeoff.

Key terms: constrained optimization, state, remaining resources, include-or-exclude decision, repeated subproblems, recurrence, best feasible portfolio, base cases, independent constraint, state space

6.4.2 Inventory control

This section shows how dynamic programming chooses inventory orders across time by accounting for both current costs and the inventory passed to future periods.

Key terms: stage, period, planning horizon, inventory, state, order quantity, immediate cost, recurrence, minimum future cost, repeated subproblems

6.4.3 Shortest routes and networks

This section explains how dynamic programming can find shortest routes in suitable networks by reusing smaller routes and progressively allowing more intermediate nodes.

Key terms: DP, shortest route, stages, state space, state, recurrence, intermediate nodes, base cases, direct connections

6.4.4 Bioinformatics and string matching

This section uses biological sequence alignment to show how dynamic programming builds a best alignment from scored choices over shorter sequence prefixes.

Key terms: bioinformatics, sequence alignment, matches, mismatches, gaps, state, recurrence, base cases, gap score, shorter sequence prefixes

6.5 Markov Decision Processes and the Bellman equation

This section extends dynamic programming from decisions with known outcomes to sequential decisions with uncertain outcomes, introducing MDPs and the Bellman equation.

Key terms: dynamic programming, next states, Markov Decision Processes, MDPs, transitions, probabilities, rewards or costs, Bellman equation, immediate reward, expected value of future states

6.5.1 Markov Decision Processes explained

This section introduces Markov Decision Processes as a way to make decisions when an action can lead to several possible next states.

Key terms: Markov chain, Markov Decision Process, action, state, reward, transition function, expected cumulative reward, Markov property, current state and action, recursive structure

6.5.2 The Bellman equation: recursive decomposition of value

This section explains how the Bellman equation combines immediate rewards with probabilistic future value to find optimal state values and actions in an MDP.

Key terms: Bellman equation, optimal value, immediate reward, expected future value, optimal substructure, discount factor, 𝛾, infinite-horizon problems, optimal policy, probabilistic

6.5.3 From dynamic programming to reinforcement learning

This section distinguishes known-model dynamic programming from reinforcement learning and shows how both retain Bellman’s recursive way of valuing decisions.

Key terms: Markov Decision Process, transition probabilities, rewards, optimal policy, reinforcement learning, Bellman’s recursive logic, Q-learning, values from experience

6.6 Dynamic programming in machine learning and AI

This section positions dynamic programming as a standalone problem-solving framework whose recursive structure is also useful for certain machine-learning and AI problems.

Key terms: dynamic programming, problem-solving framework, recursive structure, interdependent states

6.6.1 Probabilistic sequence decoding

This section shows how dynamic programming finds the most probable hidden-state sequence behind observed data without checking every possible sequence.

Key terms: probabilistic sequence decoding, Hidden Markov Model (HMM), hidden states, overlapping subproblems, Viterbi algorithm, most likely path, transitioning, observed data, probabilistic inference, most probable explanation

6.6.2 Dynamic programming’s place in modern AI

This section explains how Bellman’s recursive logic connects to modern AI while dynamic programming remains a useful framework in its own right.

Key terms: reinforcement learning, recursive conception of value, classical model-based DP, experience, dynamic programming, probabilistic inference, overlapping subproblems, optimal substructure, computational framework

6.7 Pitfalls and limitations

This section introduces why dynamic programming can remain impractical even when it turns a problem into a structured computation.

Key terms: dynamic programming, states, computation, memory, exact solutions

6.7.1 State explosion and the curse of dimensionality

This section explains how growing state spaces can make exact dynamic programming impractical and why large problems may require less exact approaches.

Key terms: state explosion, curse of dimensionality, state dimension, subproblems, exact DP, approximations, aggregation of states, tractability

6.7.2 Memory versus computation

This section explains how dynamic programming trades memory for reduced computation and how implementation choices affect that balance.

Key terms: space and time, state space, subproblems, intermediate results, memoization, tabulation, dense, tabulated recurrence, optimal value, reconstructing the decisions

6.7.3 Defining the right state

This section explains why a dynamic programming state must be compact enough to compute with yet complete enough to support correct future decisions.

Key terms: state, state space, recurrence, Markov property, transitions, rewards

6.8 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 5: Entropy and the bit: Claude Shannon and the quantification of information Chapter 7: Beyond Bayesian inference: Raiffa, Schlaifer, and rational decision-making →

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.