Dynamic programming

Stages, states and Bellman’s principle

Break a multi-stage decision into stages and states and work backwards from the end. Bellman's principle: any part of an optimal route from a state onwards is itself optimal. The value at each state uses the best value of the next stage, with $+$ for shortest/longest, $\max(\min)$ for maximin and $\min(\max)$ for minimax.