<p>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.</p>

CC BY-SA 2.5
2011-03-27T07:47:42.740Z
tabular recursion does have a nice feel to it.
Suresh Venkat
CC BY-SA 4.0
2020-07-28T18:05:04.720Z
Someone down below compared it with induction. How about inductive tabulated recursion?
Srikanth
CC BY-SA 2.5
2011-03-27T07:45:03.507Z
2011-03-27T07:45:03.507Z
Daniel Marx
<p><strong>Memoization</strong> is a fairly common variant. </p>

CC BY-SA 2.5
2011-03-25T00:04:47.540Z
Memoization is used, but does not characterize dp.
Jack
CC BY-SA 2.5
2011-03-25T03:12:09.230Z
Exactly.  Memoization is dynamic programming by accident.
Jeffε
CC BY-SA 2.5
2011-03-25T11:51:29.627Z
@professor erickson - very well said. i cannot stop laughing.
Akash Kumar
CC BY-SA 2.5
2011-03-26T15:40:44.163Z
Still, if we get to choose a new name for DP, then using memoization would be quite fitting for it. E.g. "edit distance can be computed in poly-time using memoization".
Noam
CC BY-SA 3.0
2014-02-07T03:42:32.990Z
Dynamic programming is a special case of memoization, plus explicitly directing control flow instead of following the natural applicative evaluation order. It's a shame it's usually taught the way it is, as it puts too much emphasis on filling out a table, instead of the recursive specification. It comes across as magical.
Neil Toronto
CC BY-SA 2.5
2011-03-24T23:00:08.027Z
2011-03-24T23:00:08.027Z
Suresh Venkat
<p>To go with <em>divide-and-conquer</em>, I would say <em>splice-and-combine.</em> </p>

<p>I usually use both words, <em>splice</em> and <em>combine</em> while teaching/explaining DP; but not used splice-and-combine explicitly. Sometimes I have used <em>overlapping-divide-and-conquer</em> to contrast the two paradigms. </p>

CC BY-SA 2.5
2011-03-26T03:56:14.207Z
2011-03-26T03:56:14.207Z
V Vinay
<p>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:<br>
Multiway-Divide and Memoized-Conquer (aka Divide^M &amp; Conquer^M), and<br> 
Merge all subproblems (aka Merge_all)</p>

CC BY-SA 2.5
2011-03-26T10:15:13.687Z
I do not think that creating a strong association with usual divide & conquer (as in Mergesort) is a good idea. There, subproblems are solved independently and only two results are merged. In DP, the checked subproblems are not independent and all combinations are checked. (both in rough terms). Therefore I think a name should highlight the difference rather than creating a sense of similarity.
Raphael
CC BY-SA 2.5
2011-03-26T12:28:55.837Z
@Raphael, I share the concern about the dangers of creating a strong association, but disagree with your statement of the differences.  In DP it is crucial that the subproblems _are_ "solved independently" even though solutions to subsubproblems are shared.  I usually point that if some oracle told you the right division, it would be divide and conquer, but since I don't speak Greek (unlike my PhD advisor), I have to try all possible divisions.
Jack
CC BY-SA 2.5
2011-03-26T12:46:59.110Z
Yes, subproblems are *conceptually* independent. However, I was relating to them using the same partial results, as you point out. This separates DP from D&C, since it is e.g. possible to parallelise the latter without computing subproblems multiple times (or communicating the results) as opposed to the former. Your analogy is nice but does not warrant the name in this case as finding the correct divisions is an essential part of the problem. I suppose you could say that DP is a generalisation of D&C based on that reasoning, though.
Raphael
CC BY-SA 2.5
2011-03-26T21:36:03.073Z
@Raphael, sorry to be pedantic, but since this is a question about teaching, I want the notion of subproblem independence to be clear, and just saying "conceptually independent" is not precise. When you try a division, the subproblems you produce may not have dependencies.  Your other comments focus on the steps of DP algorithms; I prefer to focus first on precisely defining the problem to be solved.  My favorite examples: min weight triangulation and min convex decomposition of simple polygons (http://www.cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html)
Jack
CC BY-SA 2.5
2011-03-26T22:38:44.893Z
It is ok to be pendantic. But consider the didactic import of the choice of words: you tell the students that subproblems are independent and then give them an algorithm that does *not* separate their computation, but in fact relies heavily on "interleaved" computation. I think that can be very confusing. Therefore, you really have to separate conceptual/mathematical/optimisation/... and computational independence at some point.
Raphael
CC BY-SA 2.5
2011-03-27T07:37:08.537Z
Reference to divide and conquer is relevant in some cases (for example minimum weight triangulation), but is very misleading in many other cases, where we are essentially extending a solution step by step (e.g., pseudopolynomial algorithm for subset sum, dynamic programing on path decompositions).
Daniel Marx
CC BY-SA 2.5
2011-03-25T22:09:47.857Z
2011-03-25T22:09:47.857Z
Jack
<p><a href="http://www.cs.toronto.edu/~bor/Papers/pBT.pdf" rel="nofollow">This paper</a> (<a href="http://dx.doi.org/10.1007/s00037-011-0028-y" rel="nofollow">paywalled doi</a>) calls <em>problems</em> that can be attacked using DP "decomposable".</p>

CC BY-SA 3.0
2011-03-25T03:43:57.107Z
2014-02-07T03:07:59.047Z
2014-02-07T03:07:59.047Z
Yuval Filmus
<p>I discussed this with some colleagues recently, and after a heated discussion we came up with <strong>tabular call caching</strong>.</p>

CC BY-SA 3.0
2011-04-08T21:49:10.593Z
that sounds like something you do at an outsourced call center ;)
Suresh Venkat
CC BY-SA 3.0
2011-04-08T18:29:13.243Z
2011-04-08T18:29:13.243Z
Kevin Wortman
<p>I'd suggest name <strong>Inductive Programming</strong> -- as a kind of smth of bridge-like from our times to old good times of Euler, Kepler et al. Or maybe even <strong>Reverse Inductive Programming</strong>. 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.</p>

CC BY-SA 3.0
2011-04-12T17:07:30.300Z
my main problem with DP is the P. so I'm not a fan of this idea..
Suresh Venkat
CC BY-SA 3.0
2011-04-12T13:12:39.420Z
2011-04-12T14:18:04.413Z
2011-04-12T14:18:04.413Z
trg787
<p>I'd name it "Forward recursion with memoization".</p>

CC BY-SA 3.0
2014-02-06T08:23:35.150Z
2014-02-06T08:23:35.150Z
Benjamin
<p>Probably something that includes the words <em>table</em> and <em>fill</em>, as this is what happens.</p>

CC BY-SA 2.5
2011-03-25T03:13:05.483Z
Bah.  Dynamic programming isn't about *tables*; it's about smart recursion.
Jeffε
CC BY-SA 2.5
2011-03-25T09:07:09.790Z
Which is implemented using tables in all cases I have seen. Others have already stated that there is more to DP; so please, enlighten us!
Raphael
CC BY-SA 2.5
2011-03-25T16:42:03.400Z
I think the point is that the tables are used to implement the smart recursion. So it's the recursion that's key.
Suresh Venkat
CC BY-SA 2.5
2011-03-25T16:46:00.433Z
The recursion in itself (as I know it) is utterly unremarkable. Only the smart way of computing and storing values "one after the other" makes for an efficient algorithm. Therefore, a name should pinpoint this process rather than the computed entity, imho.
Raphael
CC BY-SA 2.5
2011-03-25T21:12:33.433Z
That's a strong statement. I'd argue that the recursion is often key, because you have to find the right set of sub problems to guarantee the optimal substructure. Of course this has the feel of a chicken and egg argument.
Suresh Venkat
CC BY-SA 2.5
2011-03-25T23:46:05.000Z
Agreed. Still, even a "good" recursion is probably slow to evaluate if approached naively. But you are right: both are needed, the "trick" and the recursion the trick is applicable to.
Raphael
CC BY-SA 2.5
2011-03-26T02:34:47.523Z
I feel it's better to separate two aspects: "Extracting a recursive structure from the problem, and writing down as a recurrence" (modeling) and "Solving the obtained recurrence in a bottom-up way" (algorithms).  I feel dynamic programming (in algorithms) refers to both, and this is also the case for linear programming, integer programming, semidefinite programming, etc.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-26T03:15:17.743Z
Tables are *sometimes* used.  Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table [=array] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees.  Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.
Jeffε
CC BY-SA 2.5
2011-03-26T10:17:36.727Z
JeffE, a name for a technique hardly ever covers all applications. Take "diagonalisation", for example; in advanced applications, there is no diagonale anywhere in sight (or at least not the exclusive area of action). But I am not too much in love with "table filling", anyway, while I think it could be reasonable name for beginners.
Raphael
CC BY-SA 3.0
2014-02-11T15:50:42.087Z
My 2 cents on this topic. Dynamic programming has two distinct aspects to design algorithms. First is to understand the mechanics of dp as in: smart recursion plus memoization leading to a faster algorithm. The second aspect is how to **recognize** that a problem may admit a smart recursion and come up with it. Both are important to teach. For the latter, a common case is divide and conquer with limited interaction and in my view worthwhile to explicitly highlight.
Chandra Chekuri
CC BY-SA 2.5
2011-03-24T22:49:59.733Z
2011-03-24T22:49:59.733Z
Raphael
<p>Recursive view or Recursive horizon </p>

CC BY-SA 3.0
2014-02-06T15:53:26.170Z
Lazy horizon? You delay calculating a lot of results until they are needed. DP need not be recursive.
Chad Brewbaker
CC BY-SA 2.5
2011-03-25T23:13:52.610Z
2011-03-25T23:13:52.610Z
Mark
<p>Something like <strong>Subproblems Recursion</strong>.</p>

CC BY-SA 4.0
2024-09-02T23:29:42.790Z
2024-09-02T23:29:42.790Z
Rexcirus
<p><a href="http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf">Richard Bellman's autobiography</a> suggests that he chose the term “dynamic programming” to be intentionally distracting.</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>(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" <a href="http://www.ams.org/mathscinet-getitem?mr=50856">in 1952</a>, and <a href="http://en.wikipedia.org/wiki/Charles_Erwin_Wilson">Charles Erwin Wilson</a> did not become Secretary of Defense until 1953.)</p>

<p>Anyway, Bellman's original motivation suggests <strong>multistage planning</strong>, but at least for algorithmic purposes, I'd prefer something like <strong>frugal bottom-up recursion</strong>, only with fewer syllables.</p>

CC BY-SA 2.5
2011-03-25T03:45:16.610Z
Of course, what I'd *really* like to do is rename “Bellman's Equation”, or as computer scientists call it, “any recurrence whatsoever”.
Jeffε
CC BY-SA 3.0
2012-02-28T14:52:31.233Z
your answer was used here: http://biostar.stackexchange.com/questions/17954
Pierre
CC BY-SA 4.0
2020-10-19T17:29:13.237Z
Updated link: https://www.biostars.org/p/17908/
Nayuki
CC BY-SA 2.5
2011-03-25T03:43:36.657Z
2011-03-25T03:43:36.657Z
Jeffε
<p>If you could rename dynamic programming, what would you call it?</p>

CC BY-SA 2.5
2011-03-24T23:07:22.390Z
@Suresh, I started [a meta discussion](http://meta.cstheory.stackexchange.com/q/1074/186) about this question.
Kaveh
CC BY-SA 2.5
2011-03-24T23:17:46.750Z
I would say dynamic programming is dynamic programming.  That's a separate concept from algorithms.  If you would ask "algorithmic applications of dynamic programming", that would make more sense to me.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-25T00:01:39.023Z
Of course dp is dp, but programming and dynamic both mean something different today, so when I teach dynamic programming, I wish it had a different name.
Jack
CC BY-SA 2.5
2011-03-25T01:07:18.140Z
Sorry, I wasn't clear enough.  Are you interested in dynamic programming in general, including the use in control and policy planning, etc., and even stochastic dynamic programming, or just in dynamic programming as a method for algorithm design?  The main audience here would know the latter only, but your question is quite general that would includes the former.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-25T01:24:12.540Z
Yoshio, I think you should just explain the more general concept resp the differences in an answer as it could enlighten many of us.
Raphael
CC BY-SA 2.5
2011-03-25T01:54:19.770Z
@Raphael: Thank you for the suggestion, but I don't think that will be an answer.  Probably, it's enough to include references to Wikipedia: http://en.wikipedia.org/wiki/Dynamic_programming and http://en.wikipedia.org/wiki/Bellman_equation.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-25T21:14:13.307Z
Another not-entirely-tongue-in-cheek idea: "the thing that gets you jobs at Google" - based on the experience my students have had :)
Suresh Venkat
CC BY-SA 3.0
2011-04-09T07:53:03.017Z
There are a lot of "bad" names for things in the literature, but if the readers of your paper know what "dynamic programming" is, then you should use that name. Otherwise you'll confuse them.
Rob
CC BY-SA 3.0
2014-02-07T03:40:34.240Z
I tell my students it is smart recursion + lookup table. I think **DAG recursion** might be suitable as the main point is to do the recursion on the subproblems as a DAG in place of the the subproblem tree which can be exponentially larger.
Kaveh
<ds.algorithms><soft-question><terminology><ho.history-overview>
If you could rename dynamic programming...
Jack
# If you could rename dynamic programming...

(Asked by: username_0 on 2011-03-24)

If you could rename dynamic programming, what would you call it?

**Tags:** ds.algorithms, soft-question, terminology, ho.history-overview
> **Comments:**
> **username_1**: @Suresh, I started [a meta discussion](http://meta.cstheory.stackexchange.com/q/1074/186) about this question.  
> **username_2**: I would say dynamic programming is dynamic programming.  That's a separate concept from algorithms.  If you would ask "algorithmic applications of dynamic programming", that would make more sense to me.  
> **username_0**: Of course dp is dp, but programming and dynamic both mean something different today, so when I teach dynamic programming, I wish it had a different name.  
> **username_2**: Sorry, I wasn't clear enough.  Are you interested in dynamic programming in general, including the use in control and policy planning, etc., and even stochastic dynamic programming, or just in dynamic programming as a method for algorithm design?  The main audience here would know the latter only, but your question is quite general that would includes the former.  
> **username_3**: Yoshio, I think you should just explain the more general concept resp the differences in an answer as it could enlighten many of us.  
> **username_2**: @Raphael: Thank you for the suggestion, but I don't think that will be an answer.  Probably, it's enough to include references to Wikipedia: http://en.wikipedia.org/wiki/Dynamic_programming and http://en.wikipedia.org/wiki/Bellman_equation.  
> **username_4**: Another not-entirely-tongue-in-cheek idea: "the thing that gets you jobs at Google" - based on the experience my students have had :)  
> **username_5**: There are a lot of "bad" names for things in the literature, but if the readers of your paper know what "dynamic programming" is, then you should use that name. Otherwise you'll confuse them.  
> **username_1**: I tell my students it is smart recursion + lookup table. I think **DAG recursion** might be suitable as the main point is to do the recursion on the subproblems as a DAG in place of the the subproblem tree which can be exponentially larger.  

---

## 12 answers

### Answer by username_8 on 2011-03-25. Score: 59 | Accepted answer

[Richard Bellman's autobiography](http://www.wu-wien.ac.at/usr/h99c/h9951826/bellman_dynprog.pdf) 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](http://www.ams.org/mathscinet-getitem?mr=50856), and [Charles Erwin Wilson](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_8**: Of course, what I'd *really* like to do is rename “Bellman's Equation”, or as computer scientists call it, “any recurrence whatsoever”.  
> **username_21**: your answer was used here: http://biostar.stackexchange.com/questions/17954  
> **username_22**: Updated link: https://www.biostars.org/p/17908/  

---

### Answer by username_6 on 2011-03-27. Score: 39

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.

> **Comments:**
> **username_4**: tabular recursion does have a nice feel to it.  
> **username_7**: Someone down below compared it with induction. How about inductive tabulated recursion?  

---

### Answer by username_4 on 2011-03-24. Score: 24

**Memoization** is a fairly common variant.

> **Comments:**
> **username_0**: Memoization is used, but does not characterize dp.  
> **username_8**: Exactly.  Memoization is dynamic programming by accident.  
> **username_9**: @professor erickson - very well said. i cannot stop laughing.  
> **username_10**: Still, if we get to choose a new name for DP, then using memoization would be quite fitting for it. E.g. "edit distance can be computed in poly-time using memoization".  
> **username_11**: Dynamic programming is a special case of memoization, plus explicitly directing control flow instead of following the natural applicative evaluation order. It's a shame it's usually taught the way it is, as it puts too much emphasis on filling out a table, instead of the recursive specification. It comes across as magical.  

---

### Answer by username_12 on 2011-03-26. Score: 11

To go with *divide-and-conquer*, I would say *splice-and-combine.*

I usually use both words, *splice* and *combine* while teaching/explaining DP; but not used splice-and-combine explicitly. Sometimes I have used *overlapping-divide-and-conquer* to contrast the two paradigms.


---

### Answer by username_0 on 2011-03-25. Score: 9

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)

> **Comments:**
> **username_3**: I do not think that creating a strong association with usual divide & conquer (as in Mergesort) is a good idea. There, subproblems are solved independently and only two results are merged. In DP, the checked subproblems are not independent and all combinations are checked. (both in rough terms). Therefore I think a name should highlight the difference rather than creating a sense of similarity.  
> **username_0**: @Raphael, I share the concern about the dangers of creating a strong association, but disagree with your statement of the differences.  In DP it is crucial that the subproblems _are_ "solved independently" even though solutions to subsubproblems are shared.  I usually point that if some oracle told you the right division, it would be divide and conquer, but since I don't speak Greek (unlike my PhD advisor), I have to try all possible divisions.  
> **username_3**: Yes, subproblems are *conceptually* independent. However, I was relating to them using the same partial results, as you point out. This separates DP from D&C, since it is e.g. possible to parallelise the latter without computing subproblems multiple times (or communicating the results) as opposed to the former. Your analogy is nice but does not warrant the name in this case as finding the correct divisions is an essential part of the problem. I suppose you could say that DP is a generalisation of D&C based on that reasoning, though.  
> **username_0**: @Raphael, sorry to be pedantic, but since this is a question about teaching, I want the notion of subproblem independence to be clear, and just saying "conceptually independent" is not precise. When you try a division, the subproblems you produce may not have dependencies.  Your other comments focus on the steps of DP algorithms; I prefer to focus first on precisely defining the problem to be solved.  My favorite examples: min weight triangulation and min convex decomposition of simple polygons (http://www.cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html)  
> **username_3**: It is ok to be pendantic. But consider the didactic import of the choice of words: you tell the students that subproblems are independent and then give them an algorithm that does *not* separate their computation, but in fact relies heavily on "interleaved" computation. I think that can be very confusing. Therefore, you really have to separate conceptual/mathematical/optimisation/... and computational independence at some point.  
> **username_6**: Reference to divide and conquer is relevant in some cases (for example minimum weight triangulation), but is very misleading in many other cases, where we are essentially extending a solution step by step (e.g., pseudopolynomial algorithm for subset sum, dynamic programing on path decompositions).  

---

### Answer by username_13 on 2011-03-25. Score: 5

[This paper](http://www.cs.toronto.edu/~bor/Papers/pBT.pdf) ([paywalled doi](http://dx.doi.org/10.1007/s00037-011-0028-y)) calls *problems* that can be attacked using DP "decomposable".


---

### Answer by username_14 on 2011-04-08. Score: 4

I discussed this with some colleagues recently, and after a heated discussion we came up with **tabular call caching**.

> **Comments:**
> **username_4**: that sounds like something you do at an outsourced call center ;)  

---

### Answer by username_15 on 2011-04-12. Score: 4

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.

> **Comments:**
> **username_4**: my main problem with DP is the P. so I'm not a fan of this idea..  

---

### Answer by username_16 on 2014-02-06. Score: 2

I'd name it "Forward recursion with memoization".


---

### Answer by username_3 on 2011-03-24. Score: 2

Probably something that includes the words *table* and *fill*, as this is what happens.

> **Comments:**
> **username_8**: Bah.  Dynamic programming isn't about *tables*; it's about smart recursion.  
> **username_3**: Which is implemented using tables in all cases I have seen. Others have already stated that there is more to DP; so please, enlighten us!  
> **username_4**: I think the point is that the tables are used to implement the smart recursion. So it's the recursion that's key.  
> **username_3**: The recursion in itself (as I know it) is utterly unremarkable. Only the smart way of computing and storing values "one after the other" makes for an efficient algorithm. Therefore, a name should pinpoint this process rather than the computed entity, imho.  
> **username_4**: That's a strong statement. I'd argue that the recursion is often key, because you have to find the right set of sub problems to guarantee the optimal substructure. Of course this has the feel of a chicken and egg argument.  
> **username_3**: Agreed. Still, even a "good" recursion is probably slow to evaluate if approached naively. But you are right: both are needed, the "trick" and the recursion the trick is applicable to.  
> **username_2**: I feel it's better to separate two aspects: "Extracting a recursive structure from the problem, and writing down as a recurrence" (modeling) and "Solving the obtained recurrence in a bottom-up way" (algorithms).  I feel dynamic programming (in algorithms) refers to both, and this is also the case for linear programming, integer programming, semidefinite programming, etc.  
> **username_8**: Tables are *sometimes* used.  Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table [=array] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees.  Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.  
> **username_3**: JeffE, a name for a technique hardly ever covers all applications. Take "diagonalisation", for example; in advanced applications, there is no diagonale anywhere in sight (or at least not the exclusive area of action). But I am not too much in love with "table filling", anyway, while I think it could be reasonable name for beginners.  
> **username_17**: My 2 cents on this topic. Dynamic programming has two distinct aspects to design algorithms. First is to understand the mechanics of dp as in: smart recursion plus memoization leading to a faster algorithm. The second aspect is how to **recognize** that a problem may admit a smart recursion and come up with it. Both are important to teach. For the latter, a common case is divide and conquer with limited interaction and in my view worthwhile to explicitly highlight.  

---

### Answer by username_18 on 2011-03-25. Score: 1

Recursive view or Recursive horizon

> **Comments:**
> **username_19**: Lazy horizon? You delay calculating a lot of results until they are needed. DP need not be recursive.  

---

### Answer by username_20 on 2024-09-02. Score: -1

Something like **Subproblems Recursion**.


---

