16
$\begingroup$

One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called like that. That is hard for me to believe.

Does it refer to the fact that the subproblems are solved during run-time and used in reaching the final goal? Like dynamic memory allocation that happens during run-time?

[ANSWER]

I should have read this wiki article before asking the question, sorry.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Short answer, it's just a name. Doesn't need to have a literal meaning. $\endgroup$
    – Yuval Filmus
    Commented Nov 10, 2013 at 8:37
  • 6
    $\begingroup$ Arguably, typical implementations of DP (table filling) are as static as an algorithm can get. $\endgroup$
    – Raphael
    Commented Nov 10, 2013 at 10:44

5 Answers 5

Reset to default
13
$\begingroup$

Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$
    – John Dvorak
    Commented Nov 10, 2013 at 8:04
  • 1
    $\begingroup$ Someone at Wikipedia seems to disagree, I just found this-It's dynamic because the values in the table are filled in by the algorithm based on other values of the table, and it's programming in the sense of setting things in a table, like how television programming is concerned with when to broadcast what shows - at Wikibooks $\endgroup$
    – kintoki
    Commented Nov 10, 2013 at 10:34
  • $\begingroup$ @akki: there are examples of dynamic programming in which a table is not needed at all... $\endgroup$
    – Massimo Cafaro
    Commented Nov 10, 2013 at 12:01
  • 1
    $\begingroup$ @akki: as an example, computing Fibonacci numbers in a bottom-up manner only requires constant $O(1)$ space in order to save the Fibonacci numbers required to compute the next one in the series; computing the Longest Common Subsequence of two strings of length $m$ and $n$ can be done using $O(min(m,n))$ space instead of the full $m n$ table and so on. $\endgroup$
    – Massimo Cafaro
    Commented Nov 10, 2013 at 16:42
  • 2
    $\begingroup$ @akki: that is exactly what I refer to when I say that DP is about smartly unwinding the recursion! But the name itself was pointless and remains pointless. $\endgroup$
    – Massimo Cafaro
    Commented Nov 10, 2013 at 18:01
6
$\begingroup$

Richard Bellman called it Dynamic Programming in the words in Bellman enter image description here

I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes.

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

Source: Eye of the Hurricane, Richard Bellman (Autobiography)

Improve this answer
$\endgroup$
0
5
$\begingroup$

There's an interesting story here.. Bellman pioneered this paradigm. But, this was actually mathematical research. Back in his day, the then secretary of defense was paranoid of the words Research and Math (crazy guy, right!). Bellman was scared that the secretart would be furious at his work and eventually would get him into trouble. So to blur things a bit, he called it Dynamic Programming, however there's nothing 'dynamic' about it..

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Source for this? Seems like a really interesting story. $\endgroup$
    – Joey Eremondi
    Commented Nov 10, 2013 at 19:07
  • $\begingroup$ Just as a side note: it seems unclear who devised Dynamic Programming for the first time. Bellman should be credited for proving that any Dynamic Programming implementation when being optimal obeys the so-called Bellman-Ford equations. Unfortunately, it seems that many people easily believe that that makes Bellman to be the main researcher behind the original idea. $\endgroup$
    – Carlos Linares López
    Commented Nov 11, 2013 at 21:30
  • $\begingroup$ @jmite i read this in some place (probably some blog).. i will try to provide the source... $\endgroup$
    – Subhayan
    Commented Nov 12, 2013 at 0:56
  • $\begingroup$ @jmite You can find the story in Jeff's lecture note of Lecture 5: Dynamic Programming and also in the wiki: dynamic programming. $\endgroup$
    – hengxin
    Commented Dec 20, 2013 at 4:32
2
$\begingroup$

Even though there is a backstory on the naming, as stated in the other answers, the term dynamic programming makes total sense. Dynamic means that something is changing. Programming means keeping a table (program or schedule), as it is implied to the term linear programming, too.

Quoting CLRS

“Programming” in this context refers to a tabular method, not to writing computer code.

So, dynamic programming is keeping a table (with the results of the sub-problems) that is being updated during the solution.

On that regard, the name could apply to any algorithm than mutates a table. It doesn't attribute any of the basic characteristics of the dynamic programming, which are optimal substructure and overlapping sub-problems. So, in the end you just cannot use it "in a pejorative sense".

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ How is this not the accepted answer? $\endgroup$
    – lolololol ol
    Commented Jul 25, 2023 at 16:34
1
$\begingroup$

I always intuited that it meant that algorithms using dynamic programming seemed to edit the problem space "dynamically" until the problem could be solved with a greedy algorithm.

For example, with the Checkerboard problem, the dynamic programming algorithm edits the entire board as it goes through it, and then finally, a greedy algorithm can be used (similarly, with Dijkstra's shortest-path algorithm, etc.).

I am unsure if this generalizes to every dynamic programming problem though.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.