chapter six

6 Dynamic programming: Richard Bellman and recursive optimization

 

This chapter covers

  • Richard Bellman’s Dynamic Programming (1957), which introduced and defined multi-stage decision-making
  • How dynamic programming (DP) decomposes complex problems into smaller, tractable subproblems
  • Why overlapping subproblems and optimal substructure make DP possible
  • How recursive optimization guarantees globally optimal solutions
  • How the same recurrence relation extends from classic problems to real-world sequential decisions under uncertainty

The preceding chapters traced a gradual progression from inference to action. Thomas Bayes showed how beliefs can be updated as new evidence becomes available, while Ronald Fisher developed methods for extracting information from data through estimation and likelihood. Jerzy Neyman and Egon Pearson then transformed statistical evidence into principled decisions through hypothesis testing, providing a rigorous framework for choosing among competing courses of action. Claude Shannon extended this progression by redefining information itself, showing how messages could be quantified, transmitted efficiently and reliably, and acted upon despite limited capacity, noise, and uncertainty. Richard Bellman addressed the next logical question: Given a sequence of interconnected decisions, how can the entire sequence be optimized rather than each decision considered in isolation?

6.1 The dynamic programming paradigm

6.1.1 Structural prerequisites for dynamic programming

6.1.2 Expressing problems as recurrence relations

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

6.1.4 Implementation methods

6.1.5 From principles to practice

6.2 Constrained optimization: the knapsack problem

6.2.1 Verifying prerequisites

6.2.2 Specifying the recurrence

6.2.3 Defining states, transitions, and base cases

6.2.4 Choosing an implementation strategy

6.2.5 Solving the 0/1 knapsack problem

6.2.6 Reconstructing the selected items

6.3 Counting solutions: the coin change problem

6.3.1 Verifying the prerequisites

6.3.2 Specifying the recurrence

6.3.3 Defining states, transitions, and base cases

6.3.4 Choosing an implementation strategy

6.3.5 Solving the coin change problem

6.3.6 Interpreting the solution

6.4 Real-world applications of dynamic programming

6.4.1 Constrained optimization

6.4.2 Inventory control

6.4.3 Shortest routes and networks

6.4.4 Bioinformatics and string matching

6.5 Markov Decision Processes and the Bellman equation

6.5.1 Markov Decision Processes explained

6.5.2 The Bellman equation: recursive decomposition of value

6.5.3 From dynamic programming to reinforcement learning

6.6 Dynamic programming in machine learning and AI