Why “dynamic programming”?

I've always hated the term “dynamic programming”. It's big and imposing, making a simple concept sound far more intimidating than it should. And it's completely opaque: if you didn't know the term, would you ever guess that it meant memo functions? (Yes, memoization is the right concept; see the followup.)

I always supposed it was historical, and must have made sense, in some context, at some point. Groping for some way to remember the term, I came up with a fable: if you see the cached results as part of the program, then dynamic programming involves augmenting the program at runtime. So I imagined memoization had initially been seen (or even implemented) as a form of self-modifying code, and that explained the term.

But it turns out it never made even that much sense. Richard Bellman, who coined it, explains:

An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

“Dynamic programming” never meant anything; it was nothing but a political euphemism. But somehow it became attached to one of the useful concepts Bellman discovered, and to this day, students of computer science struggle to learn that simple idea, because it's burdened with a nonsense name.

Please call it “memoization” instead. And tell your students.

(Via Wikipedia, of all places. It's not usually a good source for CS information, but it's pretty good about linking to historical sources, or at least, as in this case, to an article quoting one.)

(“Dynamic” does have some negatively connoted uses nowadays, in particular in the static type theory community — partly from the perennial flamewar rivalry with dynamic typing, and partly because the main practical purpose of static analysis is to eliminate dynamic uncertainty, so “dynamic” suggests failure.)

Several people have quoted Russell and Norvig: “This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.” Perhaps the antipathy to research did not originate with Wilson, or perhaps Bellman initially intended the term to make sense, and only later adopted it as camouflage.