Introduction to Dynamic Programming
Alexis Akira Toda · 2024
This chapter is an introduction to dynamic programming. To build intuition, it discusses specific examples such as the knapsack problem, shortest path problem, optimal savings problem, optimal stopping problem, and secretary problem. It then generalizes dynamic programs in an abstract setting and proves that any finite-horizon dynamic programming problems can be solved by backward induction.