Dynamic Programming

Dynamic Programming (DP) is the multi-stage decision-problem solution technique introduced by Richard Bellman in his 1957 book (*Dynamic Programming*, Princeton University Press); it decomposes a problem into overlapping subproblems, stores intermediate results in a table (memoisation or tabulation) and solves recursively via the Bellman equation V(s) = max_a {r(s, a) + γ V(s')}. The knapsack problem is the canonical DP example — Bellman presents the DP framework on knapsack in the 1957 book; the O(N×W) time complexity is **pseudo-polynomial** (polynomial in the value of W, exponential in its bit-length). Other canonical applications: shortest paths (Bellman-Ford), inventory (Wagner-Whitin lot-sizing), equipment replacement (Bellman 1955), stochastic decision processes (Markov Decision Process), sequence alignment in computer science (Needleman-Wunsch), parsing (CYK), matrix-chain multiplication ordering. DP comes in two main flavours: **deterministic DP** (each stage has a known outcome) and **stochastic DP** (each stage has a probabilistic outcome — Markov Decision Processes). Two conditions for DP applicability: optimal substructure (subproblem optima combine into a global optimum) and overlapping subproblems (subproblems recur). Approximate Dynamic Programming (ADP) and Stochastic Dual Dynamic Programming (SDDP) extend DP to large-scale stochastic problems. Bellman 1957 + Bellman and Dreyfus 1962 + Bertsekas 1995 are the canonical references.