Dynamic Programming Algorithm

The Problem

Dynamic programming is the workhorse of quant interviews \u2014 it powers American-option pricing, optimal-stopping puzzles, and short-rate trees. Before we deploy it, let's pin down the framework.

Questions

1. What two structural properties must a problem satisfy for dynamic programming to apply?
2. Write the Bellman equation for a state $s$, action $a$, reward $r(s,a)$, discount factor $\gamma$, and transition kernel $P(s^{\prime }\mid s,a)$.
3. List, in order, the four canonical steps for designing a DP algorithm.