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.
Memoization != dynamic programmingReplyDelete
To be more precise, memoization is a part of dynamic programming, but not all of it. Dynamic programming is 1) taking a naive recursive algorithm, 2) memoizing it, 3) building a data structure to hold the memo efficiently (often an array or matrix), and 4) unfolding the recursion to remove the remaining overhead. Memoization is the important step here, of course. Regardless of precise definitions, I agree that the term "dynamic programming" is a poor one -- and now I know why, thanks.ReplyDelete
Wow that makes senseReplyDelete
Also, 'static analysis' refers to what can be done without running the code with a set of inputs. To make it clearer: in digital circuit design, there's 'static timing analysis', which just traces propagation delays on the graph, picking the maximum; this may be pessimistic versus simulations with realistic inputs.ReplyDelete
The 'programming' bit comes from earlier Operations Research terminology, namely Linear Programming: http://en.wikipedia.org/wiki/Linear_programming
In Artificial Intelligence: A Modern Approach, page 685, Russell and Norvig claim:ReplyDelete
This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.
In my opinion, dynamic programming refers to things such as:ReplyDelete
- dynamically allocating memory
- using dynamic data structures such as double-linked lists which can grow (vs. memory arrays which are fixed in size)
- dynamically creating functions, objects, etc.
Pascal = (mostly) static programming
Python = dynamic programming
Of course the name shouldn't change. The meaning of the phrase has already shifted accordingly.ReplyDelete
I don't think so. It should be changed to more appropriate phrase. All new students have been confusing, including me myself as a graduate student about 10 years ago.Delete
Greedy Algorithms + Memoization = Dynamic ProgrammingReplyDelete
"Dynamic programming" has a wide range of meanings (which I suppose should not be surprising, since the name does nothing to anchor itself to one meaning), and none of them are identical to memoization. But the most interesting of its meanings — storing results of subproblems in a recursive computation — is a simple application of memoization. Isn't it less confusing to describe it that way — in terms of a simple concept with a specific and mnemonic name — than to use a confusing historical name which doesn't even reliably identify the concept?ReplyDelete
Mountains appear small from a distance.ReplyDelete
Dynamic programming is much more than memoization. People please read before you spread misinformation. DP is a algorithm derivation problem solving method.