Football and dynamic programming

We don't need no stinkin' longest common subsequence ! We'll use FOOTBALL to explain dynamic programming:

The footballcommentary.com Dynamic Programming Model is intended to provide guidance for certain decisions that arise during a game, such as two-point conversions and going for it on fourth down. This article explains the main ideas of the Model in simplified form. [...]

The Model is built around the idea that in making decisions, we are trying to maximize our team's probability of winning the game, and the opponents are trying to minimize that probability. There are three types of situations, called states, in which the Model explicitly evaluates our probability of winning. The first type of state is when one team or the other has just gained possession. The second type is when a team has just scored a touchdown, but has not yet tried for the extra point (or points). The third type is when a team is about to kick off.