The tabular method

Dynamic programming is an important technique for writing combinatorial algorithms, in which you divide a problem into sub-problems, like in good ol’ divide-and-conquer, except that the sub-problems may overlap, so you build up a table of these problems and their solutions in order to avoid repeated work. But the name sucks: the technique is no more or less ‘dynamic’ than many other techniques, and ‘programming’ is a fossil: as we’ll see below, the ‘program’ referred to is the output of the technique, not the implementation of the technique itself. I can recall being confused by the name when studying algorithms as an undergraduate: I knew that ‘linear programming’ referred to the optimization of linear functions under linear constraints, but what did the ‘dynamic’ in ‘dynamic programming’ refer to? The name was a small but genuine barrier to understanding the technique.

( So where did the name come from? )