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.


  1. Memoization != dynamic programming

    1. I am glad that I saw this post. It is informative blog for us and we need this type of blog thanks for share this blog, Keep posting such instructional blogs and I am looking forward for your future posts. Python Projects for Students Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account. Project Center in Chennai

  2. 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.

  3. Wow that makes sense

  4. 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.

    The 'programming' bit comes from earlier Operations Research terminology, namely Linear Programming: http://en.wikipedia.org/wiki/Linear_programming

  5. In Artificial Intelligence: A Modern Approach, page 685, Russell and Norvig claim:

    This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.

  6. In my opinion, dynamic programming refers to things such as:

    - 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

  7. Of course the name shouldn't change. The meaning of the phrase has already shifted accordingly.

    - Paddy.

    1. 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.

  8. Greedy Algorithms + Memoization = Dynamic Programming

  9. "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?

  10. Mountains appear small from a distance.

    Dynamic programming is much more than memoization. People please read before you spread misinformation. DP is a algorithm derivation problem solving method.


  11. Very Informative post about programming,Keep sharing such type of post.

    Devops training in pune

  12. Thank you for the useful blog. It's very interesting. Share more updates.
    Spoken English Classes In T Nagar
    Spoken English Classes In Porur

  13. Good Article , keep writing and sharing such content
    DevOps Training in Pune

  14. This post is so interactive and informative.keep updating more information...
    AWS Cloud Technologies
    AWS Application Services

  15. This post is so useful and informative. Keep updating with more information.....
    Software Testing Course in Bangalore
    Best Software Testing Institute in Bangalore


  16. This article is a creative one and the concept is good to enhance our knowledge.

    DevOps Training in Chennai
    Devops Online Training
    DevOps Training in Bangalore


It's OK to comment on old posts.