Chapter 6: Dynamic programming: Richard Bellman and recursive optimization
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
- Optimization across interconnected decisions. Explain why a sequence of decisions should be optimized as a whole and how dynamic programming builds a globally optimal solution from reusable subproblem solutions.
- Problem structure and formulation. Explain why decomposition and recursion alone are insufficient for dynamic programming to work.
- Staged reusable subproblems. Explain how dynamic programming breaks a complex, multistage problem into smaller related subproblems and reuses their solutions instead of recomputing them.
- Problem formulation and fit. Describe what a problem formulation must capture for dynamic programming to be useful, and why the method is not automatically helpful for every problem.
- Reusable overlapping subproblems. Explain how repeated intermediate subproblems create redundant work and how storing each distinct result lets dynamic programming reuse it. Use the recursive computation of F6 as an illustration.
- Compositional optimal substructure. Explain that an overall optimum must be constructible from solutions to smaller subproblems, and distinguish this requirement from merely finding repeated calculations. Describe why both conditions matter when deciding whether to use dynamic programming.
- Recurrence relations as blueprints. Explain how a recurrence defines a larger problem’s solution using smaller instances, and illustrate that relationship with the Fibonacci example.
- States and state design. Explain how a state uniquely identifies a subproblem and why it should retain exactly the information needed—no less and no more. Use the Fibonacci position n as an example.
- Transitions between subproblems. Describe how transitions connect states according to the recurrence, using the move from computing F6 to computing F5 and F4.
- Base cases and computation. Explain how directly known base cases stop decomposition and anchor evaluation of the remaining states, including F0 = 0 and F1 = 1 for Fibonacci.
- Bottom-up and top-down evaluation. Trace how tabulation works forward from known base cases and how memoization works backward from the requested problem, storing results so repeated subproblems are not recomputed.
- Implementation choice and tradeoffs. Explain why two mathematically equivalent implementations can differ in practical performance, and distinguish the conditions favoring tabulation from those favoring memoization.
- Structural formulation of dynamic programming. Explain why applying dynamic programming depends on recognizing overlapping subproblems and optimal substructure, then formulating a recurrence, states, transitions, and base cases before implementation.
- Dynamic versus linear programming. Distinguish dynamic programming’s sequence of interconnected subproblems from linear programming’s simultaneous optimization of variables under linear constraints, and explain what guides the choice between them.
- Zero One Knapsack Formulation. Describe how item weights and values, a fixed capacity, and take-or-leave choices define the objective of the 0/1 knapsack problem.
- Optimization Method Tradeoffs. Distinguish why greedy selection, brute-force enumeration, and dynamic programming differ as approaches to the knapsack problem.
- Overlapping knapsack subproblems. Explain why recursive include-or-exclude decisions can reach the same knapsack state more than once, and how dynamic programming avoids repeating the work.
- Knapsack optimal substructure. Explain how the best value for a knapsack state is built by comparing the optimal outcomes of excluding and, when feasible, including the current item.
- Knapsack include-or-exclude recurrence. Explain what V(i, c) represents and how the recurrence chooses a value when item i is too heavy or fits within capacity c.
- Knapsack State Meaning. Explain what the state (i, c) and its value V(i, c) mean in the 0/1 knapsack problem.
- Include And Exclude Transitions. Trace the smaller state reached when item i is excluded and the smaller state reached when it is included.
- Zero Value Boundary Cases. State the two knapsack base cases and explain why each has value zero.
- Knapsack table construction. Describe what the rows, columns, and cells of the knapsack table represent, and trace how it is filled from the base cases to the final state.
- Dense state space preference. Justify why the section favors tabulation over memoization for the 0/1 knapsack problem.
- Include versus exclude comparisons. Explain how the table compares excluding an item with including its value plus a previously solved value at the remaining capacity, using Items 2 and 3 as examples.
- Final optimum and its limit. Trace the last comparison at capacity 7 and distinguish the optimal value reported by the table from the item combination that achieves it.
- Knapsack item backtracking. Trace how backtracking recovers one optimal set of items from the completed knapsack table, including what happens when adjacent-row values differ or are equal.
- Counting versus optimizing coin change. Distinguish the coin change version that minimizes the number of coins from the version that counts every distinct combination producing a target amount.
- Distinct combinations versus arrangements. Explain why different orders of the same coins count as one solution in this coin change problem.
- Repeated remaining amounts. Explain how different coin combinations can lead to the same remaining amount and why reusing a count computed for that amount avoids repeated work.
- Counts built from smaller counts. Explain why the subsection treats coin change as having the required substructure even though its objective is counting rather than optimization.
- Coin-change recurrence contributions. Explain what ways[n] counts and how an eligible coin denomination contributes a count from the remaining amount n − c.
- Combination counting versus permutations. Distinguish adding contributions in coin change from choosing the larger value in knapsack, and explain why update order must prevent duplicate counts.
- Coin Change States and Transitions. Explain what ways[n] records and how considering a coin denomination updates the count for an amount.
- Zero Amount Base Case. Justify why ways[0] is one and explain its role in starting the tabulated counts.
- Denomination-first tabulation order. Describe the order of updates in coin-change tabulation and explain why it counts combinations rather than permutations.
- Denomination By Denomination Updates. Trace how processing the 1-, 5-, and 10-unit coins changes the counts, and explain how the final value ways[12] = 4 is reached.
- Four coin combinations. Explain why ways[12] = 4 for coins worth 1, 5, and 10 units by grouping combinations according to their larger coins and treating different orders of the same coins as one solution.
- Counting versus optimizing. Distinguish the coin-change objective from the knapsack objective, including why the count needs no backtracking to recover a preferred selection.
- Shared Framework Across Applications. Explain that real-world dynamic programming retains the framework illustrated by knapsack and coin change, even when problems involve additional constraints, longer decision horizons, larger state spaces, or more complex relationships among decisions.
- Multi-resource project states. Explain how dynamic programming can represent a project-funding decision with several constraints by tracking each remaining resource in the state and updating applicable resources when a project is included or excluded.
- Reusable portfolio subproblems. Describe why the knapsack-style include-or-exclude recurrence still works with multiple constraints, including when subproblem results can be reused and when a base case yields no additional value.
- Order quantity cost recurrence. Describe how an inventory DP compares possible order quantities using the current period, available inventory, immediate cost, and the future cost of the resulting inventory level.
- Reusable states and endpoint. Explain why inventory planning has reusable subproblems and how an end-of-horizon base case supports working backward.
- Pairwise Route Update. Trace how the shortest-route example defines its state, starts from direct connections, and updates a route when another intermediate node is permitted.
- Alignment states and choices. Trace how a dynamic programming state, its three alignment choices, and its base cases contribute to a best alignment.
- Reusable prefix alignments. Explain why storing optimal alignments of shorter prefixes avoids searching every complete alignment, and identify the stated scalability caveat.
- MDP representation of uncertainty. Describe how a Markov Decision Process represents possible state transitions, their probabilities, and associated rewards or costs rather than specifying just one next state.
- Bellman equation under uncertainty. Explain that the Bellman equation relates the best current action to its immediate reward and the expected value of future states, preserving dynamic programming’s objective of optimization under uncertainty.
- Decisions in probabilistic transitions. Distinguish a Markov Decision Process from a Markov chain: a chain describes probabilistic movement among states, while an MDP adds actions whose rewards and next-state probabilities may differ.
- Markov property and state. Explain why an MDP's current state must capture the past information relevant to predicting the next state, and how that supports dynamic programming's recursive structure.
- Expected value of possible futures. Explain how evaluating an action under uncertain outcomes differs from evaluating a single predetermined next state: consider each possible future state's value together with its probability.
- Recursive optimal state value. Explain how the Bellman equation evaluates each available action by adding its immediate reward to the discounted, probability-weighted values of possible next states, then takes the largest total as the state's optimal value.
- Known versus unknown models. Distinguish uncertainty in an action’s outcome from uncertainty about the MDP model, and explain why classical dynamic programming can use the Bellman equation when transition probabilities and rewards are known.
- Experience-based Bellman values. Describe how reinforcement learning improves decisions through interaction and explain how estimating values from experience preserves Bellman’s recursive logic.
- Dynamic programming’s role in AI. Explain how dynamic programming’s role in machine learning and AI differs from that of maximum likelihood estimation or entropy, and identify the kind of problem for which its recursive structure is useful.
- Viterbi path probability updates. Trace how the Viterbi algorithm reuses the best path to each hidden state and updates its probability at the next sequence position. Explain how repeating these updates identifies the globally most probable path without enumerating all sequences.
- Recursive value in reinforcement learning. Explain how many reinforcement learning methods retain Bellman’s relationship between present and future value even when the model is not known in advance.
- Dynamic programming’s independent role. Describe why dynamic programming remains useful beyond its incorporation into newer learning methods, and identify the kind of problems to which the section says it applies.
- Limits of exact dynamic programming. Explain why structuring a problem with dynamic programming does not guarantee a practical exact solution, naming the three challenges identified here.
- State space growth. Explain how adding state variables, independent constraints, or finer detail increases the number of dynamic programming subproblems.
- Exactness and tractability tradeoff. Explain why a valid DP formulation may be impractical to solve exactly and what broad kinds of compromise the section identifies.
- Space and time trade-off. Explain why storing subproblem results makes dynamic programming faster but uses more memory, especially as the state space expands.
- State completeness and tractability. Explain how to choose what belongs in a dynamic programming state: it must retain information needed for future transitions, rewards, and decisions without unnecessarily enlarging the state space. Describe why relevant history must be captured in the state or elsewhere in the model.
Section by section
Introduction
The introduction frames dynamic programming as Bellman’s way to optimize interconnected decisions by reusing solutions to smaller problems.
- Optimization across interconnected decisions: Explain why a sequence of decisions should be optimized as a whole and how dynamic programming builds a globally optimal solution from reusable subproblem solutions.
Why it matters: It explains why solving smaller problems can address an entire sequence of dependent choices. - Problem structure and formulation: Explain why decomposition and recursion alone are insufficient for dynamic programming to work.
Why it matters: It prevents treating dynamic programming as a recipe that works whenever a problem can be split into pieces.
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.
- Staged reusable subproblems: Explain how dynamic programming breaks a complex, multistage problem into smaller related subproblems and reuses their solutions instead of recomputing them.
Why it matters: This is the central reason the section gives for structuring a problem dynamically rather than tackling it all at once. - Problem formulation and fit: Describe what a problem formulation must capture for dynamic programming to be useful, and why the method is not automatically helpful for every problem.
Why it matters: The section emphasizes choosing and formulating a suitable problem before focusing on an algorithm’s mechanics. - Bellman’s RAND setting: Describe how the multistage planning and resource-allocation problems Bellman encountered at RAND helped motivate dynamic programming, and where he saw similar problems beyond defense.
Why it matters: The history shows that the idea arose from practical decision problems with uses beyond its original 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.
- Reusable overlapping subproblems: Explain how repeated intermediate subproblems create redundant work and how storing each distinct result lets dynamic programming reuse it. Use the recursive computation of F6 as an illustration.
Why it matters: Repeated subproblems are what make stored results useful rather than extra bookkeeping. - Compositional optimal substructure: Explain that an overall optimum must be constructible from solutions to smaller subproblems, and distinguish this requirement from merely finding repeated calculations. Describe why both conditions matter when deciding whether to use dynamic programming.
Why it matters: Reusing smaller answers is not enough if those answers cannot produce the best overall solution.
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.
- Recurrence relations as blueprints: Explain how a recurrence defines a larger problem’s solution using smaller instances, and illustrate that relationship with the Fibonacci example.
Why it matters: Identifying the relationship between larger and smaller solutions gives dynamic programming a problem-specific blueprint to evaluate.
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.
- States and state design: Explain how a state uniquely identifies a subproblem and why it should retain exactly the information needed—no less and no more. Use the Fibonacci position n as an example.
Why it matters: Choosing the right state is central to getting a correct solution without creating needless subproblems. - Transitions between subproblems: Describe how transitions connect states according to the recurrence, using the move from computing F6 to computing F5 and F4.
Why it matters: Transitions make the dependencies in a recurrence explicit so the subproblems can be evaluated systematically. - Base cases and computation: Explain how directly known base cases stop decomposition and anchor evaluation of the remaining states, including F0 = 0 and F1 = 1 for Fibonacci.
Why it matters: Known starting values give the recurrence a stopping point and make its other values computable.
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.
- Bottom-up and top-down evaluation: Trace how tabulation works forward from known base cases and how memoization works backward from the requested problem, storing results so repeated subproblems are not recomputed.
Why it matters: The evaluation order determines which subproblems are computed and how their answers are reused. - Implementation choice and tradeoffs: Explain why two mathematically equivalent implementations can differ in practical performance, and distinguish the conditions favoring tabulation from those favoring memoization.
Why it matters: Choosing how to evaluate a recurrence can affect efficiency and ease of implementation without changing the solution.
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.
- Structural formulation of dynamic programming: Explain why applying dynamic programming depends on recognizing overlapping subproblems and optimal substructure, then formulating a recurrence, states, transitions, and base cases before implementation.
Why it matters: A sound formulation determines whether the implementation solves the intended problem. - Dynamic versus linear programming: Distinguish dynamic programming’s sequence of interconnected subproblems from linear programming’s simultaneous optimization of variables under linear constraints, and explain what guides the choice between them.
Why it matters: Two methods can pursue the same optimization objective while requiring different representations of the problem.
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.
- Zero One Knapsack Formulation: Describe how item weights and values, a fixed capacity, and take-or-leave choices define the objective of the 0/1 knapsack problem.
Why it matters: These constraints define the problem that the later knapsack solution must solve. - Optimization Method Tradeoffs: Distinguish why greedy selection, brute-force enumeration, and dynamic programming differ as approaches to the knapsack problem.
Why it matters: The comparison explains the motivation for using dynamic programming instead of an apparently simpler approach. - Resource Allocation Applications: Explain how the knapsack formulation represents practical choices beyond packing physical items.
Why it matters: It shows that knapsack models a general resource-allocation decision, not just a packing puzzle.
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.
- Overlapping knapsack subproblems: Explain why recursive include-or-exclude decisions can reach the same knapsack state more than once, and how dynamic programming avoids repeating the work.
Why it matters: Recognizing repeated states explains why dynamic programming can save work on this problem. - Knapsack optimal substructure: Explain how the best value for a knapsack state is built by comparing the optimal outcomes of excluding and, when feasible, including the current item.
Why it matters: This comparison explains why solutions to smaller knapsack states can determine the best solution to a larger one.
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.
- Knapsack include-or-exclude recurrence: Explain what V(i, c) represents and how the recurrence chooses a value when item i is too heavy or fits within capacity c.
Why it matters: This rule specifies the value to compute at each knapsack state. - Optimality from smaller subproblems: Explain why repeatedly applying the knapsack recurrence can determine the optimal value without explicitly listing every item combination.
Why it matters: It connects the local include-or-exclude rule to the best value for the whole problem.
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.
- Knapsack State Meaning: Explain what the state (i, c) and its value V(i, c) mean in the 0/1 knapsack problem.
Why it matters: The meaning of each state determines what the solution is calculating. - Include And Exclude Transitions: Trace the smaller state reached when item i is excluded and the smaller state reached when it is included.
Why it matters: The two transitions show how a knapsack state connects to smaller states. - Zero Value Boundary Cases: State the two knapsack base cases and explain why each has value zero.
Why it matters: Base cases anchor the evaluation of all the other knapsack states.
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.
- Knapsack table construction: Describe what the rows, columns, and cells of the knapsack table represent, and trace how it is filled from the base cases to the final state.
Why it matters: The table layout and fill order show how the knapsack solution is built from already computed states. - Dense state space preference: Justify why the section favors tabulation over memoization for the 0/1 knapsack problem.
Why it matters: The expected density of relevant states explains the implementation choice rather than treating it as arbitrary.
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.
- Table setup and first row: Describe how the knapsack table is initialized and how Item 1's row is filled for capacities 0 through 7.
Why it matters: The boundary values and first row provide the solved subproblems for later rows. - Include versus exclude comparisons: Explain how the table compares excluding an item with including its value plus a previously solved value at the remaining capacity, using Items 2 and 3 as examples.
Why it matters: These comparisons show how previously solved smaller-capacity problems produce better values in later rows. - Final optimum and its limit: Trace the last comparison at capacity 7 and distinguish the optimal value reported by the table from the item combination that achieves it.
Why it matters: The final cell answers how much value is attainable, while identifying the items is a separate task.
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.
- Knapsack item backtracking: Trace how backtracking recovers one optimal set of items from the completed knapsack table, including what happens when adjacent-row values differ or are equal.
Why it matters: The table gives the best value, but backtracking tells you which items achieve it.
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.
- Counting versus optimizing coin change: Distinguish the coin change version that minimizes the number of coins from the version that counts every distinct combination producing a target amount.
Why it matters: The objective determines whether a dynamic programming solution should optimize a value or count possibilities. - Distinct combinations versus arrangements: Explain why different orders of the same coins count as one solution in this coin change problem.
Why it matters: Counting reordered coins separately would overstate the number of valid combinations.
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.
- Repeated remaining amounts: Explain how different coin combinations can lead to the same remaining amount and why reusing a count computed for that amount avoids repeated work.
Why it matters: Repeated smaller problems are one reason dynamic programming is useful for coin change. - Counts built from smaller counts: Explain why the subsection treats coin change as having the required substructure even though its objective is counting rather than optimization.
Why it matters: It explains why dynamic programming applies even when the desired answer is a number of combinations, not an optimum.
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.
- Coin-change recurrence contributions: Explain what ways[n] counts and how an eligible coin denomination contributes a count from the remaining amount n − c.
Why it matters: It connects the count for an amount to counts for smaller amounts. - Combination counting versus permutations: Distinguish adding contributions in coin change from choosing the larger value in knapsack, and explain why update order must prevent duplicate counts.
Why it matters: Adding counts gives the intended answer only if rearrangements of the same coins are not counted again.
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.
- Coin Change States and Transitions: Explain what ways[n] records and how considering a coin denomination updates the count for an amount.
Why it matters: This shows how counts for smaller amounts build counts for larger ones. - Zero Amount Base Case: Justify why ways[0] is one and explain its role in starting the tabulated counts.
Why it matters: The base case gives the count updates a valid starting point.
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.
- Denomination-first tabulation order: Describe the order of updates in coin-change tabulation and explain why it counts combinations rather than permutations.
Why it matters: The update order determines whether the count represents distinct coin combinations or also counts rearrangements of the same coins.
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.
- Coin Change Table Initialization: Explain why the table starts with ways[0] = 1 and zero for every positive amount through 12.
Why it matters: These starting counts make the later coin-by-coin updates possible. - Denomination By Denomination Updates: Trace how processing the 1-, 5-, and 10-unit coins changes the counts, and explain how the final value ways[12] = 4 is reached.
Why it matters: The worked updates show how smaller-amount counts build the answer without discarding combinations already found.
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.
- Four coin combinations: Explain why ways[12] = 4 for coins worth 1, 5, and 10 units by grouping combinations according to their larger coins and treating different orders of the same coins as one solution.
Why it matters: Listing the cases checks what the computed count actually represents. - Counting versus optimizing: Distinguish the coin-change objective from the knapsack objective, including why the count needs no backtracking to recover a preferred selection.
Why it matters: It shows that dynamic programming can count valid solutions as well as optimize a decision.
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.
- Shared Framework Across Applications: Explain that real-world dynamic programming retains the framework illustrated by knapsack and coin change, even when problems involve additional constraints, longer decision horizons, larger state spaces, or more complex relationships among decisions.
Why it matters: This distinction helps connect the small worked examples to less tidy practical problems.
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.
- Multi-resource project states: Explain how dynamic programming can represent a project-funding decision with several constraints by tracking each remaining resource in the state and updating applicable resources when a project is included or excluded.
Why it matters: Tracking all relevant limits prevents an appealing project from being treated as feasible when it violates another constraint. - Reusable portfolio subproblems: Describe why the knapsack-style include-or-exclude recurrence still works with multiple constraints, including when subproblem results can be reused and when a base case yields no additional value.
Why it matters: The richer portfolio problem remains a dynamic programming problem because its feasible continuations can be solved and reused. - Constraint dimensionality cost: Explain the tradeoff between modeling more resource limits and the amount of computation dynamic programming may require.
Why it matters: A more faithful model of resource limits may be much harder to compute.
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.
- Inventory stages across time: Distinguish inventory planning stages from the item-by-item stages of knapsack, and explain why an order in one period affects later decisions.
Why it matters: It explains why ordering decisions must be judged across a planning horizon, not in isolation. - Order quantity cost recurrence: Describe how an inventory DP compares possible order quantities using the current period, available inventory, immediate cost, and the future cost of the resulting inventory level.
Why it matters: An order that looks cheapest today may be costly once future shortages or holding costs are considered. - Reusable states and endpoint: Explain why inventory planning has reusable subproblems and how an end-of-horizon base case supports working backward.
Why it matters: Reuse and a defined endpoint make the multi-period ordering problem amenable to dynamic programming.
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.
- Routing Problem Decomposition: Explain why many, but not all, network routing problems suit dynamic programming and how network stages differ from stages based on items or time.
Why it matters: It shows what makes dynamic programming useful for some routing problems rather than treating every possible path independently. - Pairwise Route Update: Trace how the shortest-route example defines its state, starts from direct connections, and updates a route when another intermediate node is permitted.
Why it matters: This comparison is how the section turns a search over complete routes into progressive route improvements.
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.
- Sequence alignment and scoring: Describe why biological sequences are aligned and how an alignment can score matches, mismatches, and gaps rather than requiring exact character matches.
Why it matters: The scoring choices explain what the dynamic programming solution is trying to optimize. - Alignment states and choices: Trace how a dynamic programming state, its three alignment choices, and its base cases contribute to a best alignment.
Why it matters: These states and choices turn alignment into smaller decisions whose best results can be combined. - Reusable prefix alignments: Explain why storing optimal alignments of shorter prefixes avoids searching every complete alignment, and identify the stated scalability caveat.
Why it matters: Reuse is why the many possible gap placements need not be searched one complete alignment at a time.
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.
- Known versus uncertain outcomes: Distinguish earlier dynamic programming examples, where a decision has a known consequence, from problems where an action can lead to several possible next states with different probabilities and consequences.
Why it matters: This distinction explains why the earlier dynamic programming examples need to be extended. - MDP representation of uncertainty: Describe how a Markov Decision Process represents possible state transitions, their probabilities, and associated rewards or costs rather than specifying just one next state.
Why it matters: Representing possible outcomes is what lets dynamic programming incorporate uncertainty into decisions. - Bellman equation under uncertainty: Explain that the Bellman equation relates the best current action to its immediate reward and the expected value of future states, preserving dynamic programming’s objective of optimization under uncertainty.
Why it matters: It connects the immediate choice to uncertain future outcomes without abandoning optimization.
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.
- Decisions in probabilistic transitions: Distinguish a Markov Decision Process from a Markov chain: a chain describes probabilistic movement among states, while an MDP adds actions whose rewards and next-state probabilities may differ.
Why it matters: This distinction explains why an MDP is a model for choosing, not just predicting, what happens next. - MDP components and objective: Describe the roles of state, action, reward, and transition probability in an MDP, and explain why the objective concerns expected cumulative reward rather than only an immediate payoff.
Why it matters: These components specify what a decision must take into account when its outcome is uncertain. - Markov property and state: Explain why an MDP's current state must capture the past information relevant to predicting the next state, and how that supports dynamic programming's recursive structure.
Why it matters: A suitably defined state lets a recursive solution work without carrying the entire history forward. - Expected value of possible futures: Explain how evaluating an action under uncertain outcomes differs from evaluating a single predetermined next state: consider each possible future state's value together with its probability.
Why it matters: It shows how dynamic programming can compare decisions even when their outcomes are uncertain.
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.
- Recursive optimal state value: Explain how the Bellman equation evaluates each available action by adding its immediate reward to the discounted, probability-weighted values of possible next states, then takes the largest total as the state's optimal value.
Why it matters: This is how dynamic programming handles choices whose next states are uncertain. - Future reward discounting: Describe how the discount factor changes the weight of future rewards and why discounting is useful for infinite-horizon problems.
Why it matters: The discount factor changes which actions look best when rewards arrive at different times. - Values and optimal policy: Explain how optimal state values identify an optimal policy and how the Bellman equation extends dynamic programming recurrence to probabilistic consequences.
Why it matters: State values are useful because they lead to a choice of action in each state.
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.
- Known versus unknown models: Distinguish uncertainty in an action’s outcome from uncertainty about the MDP model, and explain why classical dynamic programming can use the Bellman equation when transition probabilities and rewards are known.
Why it matters: The distinction explains why an uncertain outcome does not, by itself, require learning from experience. - Experience-based Bellman values: Describe how reinforcement learning improves decisions through interaction and explain how estimating values from experience preserves Bellman’s recursive logic.
Why it matters: Learning from experience changes how values are obtained, not the underlying way Bellman relates present and future value.
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.
- Dynamic programming’s role in AI: Explain how dynamic programming’s role in machine learning and AI differs from that of maximum likelihood estimation or entropy, and identify the kind of problem for which its recursive structure is useful.
Why it matters: This distinction helps you recognize when dynamic programming is the approach to a problem, not just a component of a learning method.
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.
- Hidden states and shared subproblems: Explain what probabilistic sequence decoding seeks to infer and why dynamic programming is useful for it. Use the speech example to distinguish observed sounds from the hidden words or linguistic states that may have produced them.
Why it matters: The shared intermediate states explain why this inference problem fits dynamic programming. - Viterbi path probability updates: Trace how the Viterbi algorithm reuses the best path to each hidden state and updates its probability at the next sequence position. Explain how repeating these updates identifies the globally most probable path without enumerating all sequences.
Why it matters: Keeping the best path to each state makes an otherwise costly sequence search tractable. - Inference as dynamic programming: Distinguish this use of dynamic programming from the earlier optimization examples while identifying the computational principle they share.
Why it matters: It shows that the same recursive approach applies to inference as well as optimization.
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.
- Recursive value in reinforcement learning: Explain how many reinforcement learning methods retain Bellman’s relationship between present and future value even when the model is not known in advance.
Why it matters: It identifies what reinforcement learning carries forward from Bellman without treating the two approaches as identical. - Dynamic programming’s independent role: Describe why dynamic programming remains useful beyond its incorporation into newer learning methods, and identify the kind of problems to which the section says it applies.
Why it matters: Bellman’s legacy includes a way to solve problems directly, not just an idea absorbed into modern AI.
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.
- Limits of exact dynamic programming: Explain why structuring a problem with dynamic programming does not guarantee a practical exact solution, naming the three challenges identified here.
Why it matters: These limits explain why a well-structured dynamic programming solution may still be difficult to use in practice.
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.
- State space growth: Explain how adding state variables, independent constraints, or finer detail increases the number of dynamic programming subproblems.
Why it matters: The way a problem is represented can determine whether its DP solution is practical to compute. - Exactness and tractability tradeoff: Explain why a valid DP formulation may be impractical to solve exactly and what broad kinds of compromise the section identifies.
Why it matters: It distinguishes a correct formulation from one that can be solved exactly with available resources.
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.
- Space and time trade-off: Explain why storing subproblem results makes dynamic programming faster but uses more memory, especially as the state space expands.
Why it matters: A faster dynamic programming solution may demand more memory than the problem allows. - Memoization and tabulation memory: Distinguish how memoization and tabulation store states, and explain when memoization's potential memory advantage disappears.
Why it matters: The memory benefit of memoization depends on how much of the state space the solution actually visits. - Memory needs of solution recovery: Describe when earlier table rows can be discarded and why recovering the decisions behind an optimal value may require additional information.
Why it matters: How much memory to save depends partly on whether you need just the answer or also the choices that led to it.
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.
- State completeness and tractability: Explain how to choose what belongs in a dynamic programming state: it must retain information needed for future transitions, rewards, and decisions without unnecessarily enlarging the state space. Describe why relevant history must be captured in the state or elsewhere in the model.
Why it matters: Even a well-written recurrence cannot give reliable decisions if its state leaves out information the future depends on.
Key terms: state, state space, recurrence, Markov property, transitions, rewards
6.8 Summary
Where this is used later
- Bellman: making global optimization tractable through decomposition (chapter 10) · the dynamic programming paradigm
- Decoding as Bayesian model comparison (chapter 10) · Provides an example of decoding a hidden sequence from observed data
Concepts explained in this chapter
- dynamic programmingDynamic programming is an algorithmic technique that solves problems by decomposing them into related subproblems and combining their solutions, often reusing computed results.
- base caseA base case is a directly known computational state that requires no further recursive decomposition.
- optimal substructureThe principle of optimality is the property that an optimal strategy can be formed from optimal decisions for the remaining stages after any state.
- overlapping subproblemAn overlapping subproblem is a repeated smaller instance generated by the decomposition of a larger computational problem.
- tabulationTabulation is a dynamic-programming implementation technique that iteratively evaluates subproblems in a predetermined dependency order and stores their results.
- stateA representation of a problem configuration that captures information needed to determine subsequent choices and outcomes.
- recurrenceA rule that defines a quantity in terms of its values for other instances.
- knapsack problemAn optimization problem that selects items to maximize total value subject to a capacity constraint.
- problem definitionProblem formulation is the process of specifying a problem's states, decisions, constraints, objectives, and relationships in a form suitable for analysis or computation.
- transitionA transition is a rule that maps a current state and a decision to a resulting state in a multi-stage computation.
- combinationA combination is a selection or grouping in which order does not matter.
- backtrackingBacktracking is a technique that reconstructs a solution by tracing stored decisions backward from a final state.
- change-making problemThe coin change problem is the computational problem of determining ways to form a target amount from a specified set of coin denominations, typically with a counting or optimization objective.
- transition probabilityThe probability of a particular next state given a current state and action.
- reward signalA reward is a numerical consequence associated with an action or state transition that represents its desirability in a decision process.
- channel capacityThe maximum rate at which information can be transmitted reliably through a communication channel under specified conditions.
- valueA projected representation of information that is combined with other values according to attention weights.
- Bellman equationThe Bellman equation is a recursive equation that expresses the value of a decision state in terms of immediate reward and the value of subsequent states.
- state spaceA state space is the collection of distinct configurations that can occur in a problem or dynamical process.
- memoizationMemoization is a dynamic-programming implementation technique that recursively evaluates only needed subproblems and caches their computed values.
- actionA choice available to a decision-maker in a decision problem.
- decoding strategyA procedure for selecting a generated token from a model’s next-token probability distribution.
- constraintA condition that restricts the feasible choices or solutions in an optimization problem.
- reinforcement learningReinforcement learning is a machine-learning approach in which an agent learns behavior through interaction with an environment and feedback about its actions.
- uncertaintyUncertainty is the lack of complete information about the state of a system, a quantity, or the outcome of an event.
- Markov decision processA Markov decision process is a model of sequential decisions in which actions influence transitions among states and rewards, with future dynamics depending on the current state and action.
- tradeoffA trade-off is a decision situation in which improving one outcome requires accepting a reduction in another.
- model weightA learned numerical coefficient that controls an input’s contribution in a neural network.
- cumulative rewardExpected cumulative reward is the probability-weighted expected total of rewards accumulated over a decision process.
- sequential decision-makingSequential decision-making is the selection of actions over multiple stages where each action affects later states, options, or outcomes.
- policyA policy is a rule that specifies how decisions are selected as a process moves through stages or states.
- objective functionA training objective is a quantity that a learning procedure seeks to optimize while fitting a model.
- approximationApproximation is a technique for obtaining a tractable solution by accepting some deviation from an exact result.
- permutationA permutation is an arrangement of objects or outcomes in which order matters.
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.
