If you could rename dynamic programming, what would you call it?
Richard Bellman's autobiography suggests that he chose the term “dynamic programming” to be intentionally distracting.
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.
(As Russell and Norvig point out in their AI textbook, however, this story must be a creative embellishment of the truth. Bellman first used the phrase "dynamic programming" in 1952, and Charles Erwin Wilson did not become Secretary of Defense until 1953.)
Anyway, Bellman's original motivation suggests multistage planning, but at least for algorithmic purposes, I'd prefer something like frugal bottom-up recursion, only with fewer syllables.
There are two important aspects of DP: (1) defining the subproblems (i.e., setting up a "table", which could be a multidimensional array indexed maybe by integers, vertices, subsets of vertices etc.) and (2) recursively solving the subproblems. I propose "tabular/tabulated recursion" as a name that refers to both aspects.
After my recent lecture on dynamic programming in algorithm design I had asked students to suggest a new name for this technique. While I was amused by "Tough programming," I wanted something that might make the technique more memorable. After the discussion here, I may propose two names, one for top-down and one for bottom-up:
Multiway-Divide and Memoized-Conquer (aka Divide^M & Conquer^M), and
Merge all subproblems (aka Merge_all)
I'd suggest name Inductive Programming -- as a kind of smth of bridge-like from our times to old good times of Euler, Kepler et al. Or maybe even Reverse Inductive Programming. And yes, for me DP is strongly associated with the Induction, in old good sense of the notion. Memoization, cacheing, tables etc are just elements of technique, not of the core of the approach to crack things.