It seems dynamic programming (some predetermined sequence of steps) as envisioned by Bellman is strictly less dynamic than ordinary programming today, hence the confusion?
Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate
There is another mid century term which is oddly specific for something oddly general (or the other way?) "Operations Research"
Guess Bellman should have called it "Reactive Optimization", then we would have the totally appropriate "Recursive Memoization" or "Memoized Recursion"
Sri Lankan here. I used to compete in the IOI (International Olympiad in Informatics), back in the '90s.
I aced the competition in Sri Lanka, but I failed to win a medal the first time I competed internationally. I solved several problems with recursion, but these failed to complete within the strict time limits allowed.
One of the contestants from another country told me: "You needed dynamic programming to solve problems 1 and 5." I then spent the next year trying to figure out what dynamic programming was. The folks over here weren't familiar with the term. In fact, I was often asked "did you mean dynamic memory allocation?"
After a while, I managed to find a book that talked about dynamic programming, and I was like "Oh, it's recursion + storing results" and "Ah, you can also do this iteratively in certain circumstances"
Bottom line, armed with this new knowledge, I ended up winning a gold medal at IOI 2001. Fun times.
Technically, "dynamic programming" (god, I hate that term) is focused on memoization/tabulation. It doesn't necessarily require recursion or an iterative approach, although they almost always go hand-in-hand in common leetcode/hackerrank/etc exercises.
Possibly the worst named thing in computing? Not only is "programming" not referring to programming, but "dynamic" is meaningless and just there to try to make it sound fancy.
Programming terminology is in the same vein as "Linear Programming..."
As per Wikipedia, that origin story is somewhat disputed:
"According to Russell and Norvig, the above story "cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953." Also, Harold J. Kushner stated in a speech that, "On the other hand, when I asked [Bellman] the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic. Perhaps both motivations were true."
Dynamic optimality is a way more interesting concept to me. Data structures like the splay tree can effectively write the "ideal program" for accessing data based on the current use patterns by maintaining the data in a particular way over time. Instructions and data are mostly the same thing when you really think about it.
I first learned about Dynamic Programming in the algorithms and datastructures class in the first semester at uni. But the lecturer very quickly moved on to only ever refer to it as "DP". This makes me think he may have done that as to not confuse students.
Even though I knew it wasn't referring to programming I did wonder why it was called that, interesting!
The article would probably be more complete with references to similar terms "linear program" or "integer program", unless this is also a slightly different meaning?
> 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.
That reminds me of, much later, getting my first basic programming book. In communist Romania. It was titled "Let's learn interactive microelectronics" because "programming" books were considered a waste of resources and did not get approved.
Looks like someone discovered this reddit post [1] and wrote a whole blog around the top answer. Since the example is copied verbatim, it might even be an LLM that was hooked up to web search.
My favorite dynamic programming problem is computing the percent of relatedness between two people, given a set of people and a partial graph of parenthood among them (with the assumption that any relatedness not implied by the graph is zero). If seems very confusing at first, but then you realize that if A is not a descendant of B, rel(A,B)=(rel(A,father(B))+rel(A,mother(B)))/2, which allows you to compute all relatedness values from top to bottom of the graph as fast as possible.
It computed the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).
The algorithm used is a dynamic programming one, where
Each terminal type would configure the display driver according to its supported escape codes and screen update times (some terminals were REALLY SLOW inserting and deleting lines or even scrolling, and you had to send null padding to wait for it to finish).
It's infamous both for its skull-and-crossbones warning comment [designed by Brian Reed] and correspondingly poisonous complex code, and also RMS's battle with UniPress software, incorporating it into Gnu Emacs, getting threatened by UniPress, then rewriting it from scratch.
>RMS: I can't remember all the hacks that I was proud of, so I can't pick the best. But here's something I remember fondly. The last piece of Gosmacs code that I replaced was the serial terminal scrolling optimizer, a few pages of Gosling's code which was proceeded by a comment with a skull and crossbones, meaning that it was so hard to understand that it was poison. I had to replace it, but worried that the job would be hard. I found a simpler algorithm and got it to work in a few hours, producing code that was shorter, faster, clearer, and more extensible. Then I made it use the terminal commands to insert or delete multiple lines as a single operation, which made screen updating far more efficient.
There's some more discussion about it here that ended up being pretty accurate once all was said and done:
Emacs's infamous "Ultra-hot screen management package" with its "Skull and Crossbones" warning was definitely black magic!
The algorithm worked great and was well worth it over a 300 / 1200 / 2400 baud connection to a Vax 780 / 750 / etc, and as modems and computers got faster it was still useful, but at today's network bandwidths and cpu speeds it's thunderous overkill.
>7. Acknowledgements: The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.
>Bibliography: 1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.
That code was also used in Maryland Windows (a text based overlapping/tiled window system developed at the University of Maryland by Chris Torek, like Emacs - Text Editor + Window System, kind of like "screen&qu...
Thanks for sharing. I always viewed DP as finding partials to cache. Something not done a lot in day to day algos. Did not appreciate the name as being related to execution order optimization.
We have an interpreted language in which you can call "subroutines" by name. But you can build the name in you program "on the fly", for example out of data.
42 comments
[ 3.9 ms ] story [ 57.4 ms ] threadIn the first it's for optimizing a relatively small deterministic system, in the latter it is for optimizing a stochastic process.
Pretty confusing.
[0] https://en.m.wikipedia.org/wiki/Extreme_programming
Elevating "memoization+recursion" to "dynamic programming" seems like a development that Bellman didn't anticipate
https://cs.stackexchange.com/questions/99513/dynamic-program...
There is another mid century term which is oddly specific for something oddly general (or the other way?) "Operations Research"
Guess Bellman should have called it "Reactive Optimization", then we would have the totally appropriate "Recursive Memoization" or "Memoized Recursion"
I aced the competition in Sri Lanka, but I failed to win a medal the first time I competed internationally. I solved several problems with recursion, but these failed to complete within the strict time limits allowed.
One of the contestants from another country told me: "You needed dynamic programming to solve problems 1 and 5." I then spent the next year trying to figure out what dynamic programming was. The folks over here weren't familiar with the term. In fact, I was often asked "did you mean dynamic memory allocation?"
After a while, I managed to find a book that talked about dynamic programming, and I was like "Oh, it's recursion + storing results" and "Ah, you can also do this iteratively in certain circumstances"
Bottom line, armed with this new knowledge, I ended up winning a gold medal at IOI 2001. Fun times.
> *This Haskell fan’s contender is “dynamic typing” :P
Nothing is impossible!
I prefer "cached recursion".
As per Wikipedia, that origin story is somewhat disputed:
"According to Russell and Norvig, the above story "cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953." Also, Harold J. Kushner stated in a speech that, "On the other hand, when I asked [Bellman] the same question, he replied that he was trying to upstage Dantzig's linear programming by adding dynamic. Perhaps both motivations were true."
Even though I knew it wasn't referring to programming I did wonder why it was called that, interesting!
That reminds me of, much later, getting my first basic programming book. In communist Romania. It was titled "Let's learn interactive microelectronics" because "programming" books were considered a waste of resources and did not get approved.
[1] https://www.reddit.com/r/learnprogramming/comments/1ac9zbl/d...
A program can use dynamic programming to dynamically figure out the programme required to perform a computation.
https://en.wikipedia.org/wiki/Gosling_Emacs
It computed the minimal cost path through a cost matrix of string edit operations (the costs depended i.e. on the number of characters to draw, length of the escape codes to insert/delete lines/characters, padding for slow terminals, etc).
The algorithm used is a dynamic programming one, where
Each terminal type would configure the display driver according to its supported escape codes and screen update times (some terminals were REALLY SLOW inserting and deleting lines or even scrolling, and you had to send null padding to wait for it to finish).It's infamous both for its skull-and-crossbones warning comment [designed by Brian Reed] and correspondingly poisonous complex code, and also RMS's battle with UniPress software, incorporating it into Gnu Emacs, getting threatened by UniPress, then rewriting it from scratch.
https://features.slashdot.org/story/13/01/06/163248/richard-...
>Q: Give me your best hack. [...]
>RMS: I can't remember all the hacks that I was proud of, so I can't pick the best. But here's something I remember fondly. The last piece of Gosmacs code that I replaced was the serial terminal scrolling optimizer, a few pages of Gosling's code which was proceeded by a comment with a skull and crossbones, meaning that it was so hard to understand that it was poison. I had to replace it, but worried that the job would be hard. I found a simpler algorithm and got it to work in a few hours, producing code that was shorter, faster, clearer, and more extensible. Then I made it use the terminal commands to insert or delete multiple lines as a single operation, which made screen updating far more efficient.
There's some more discussion about it here that ended up being pretty accurate once all was said and done:
https://www.reddit.com/r/emacs/comments/bek5b2/til_emacs_was...
Emacs's infamous "Ultra-hot screen management package" with its "Skull and Crossbones" warning was definitely black magic!
The algorithm worked great and was well worth it over a 300 / 1200 / 2400 baud connection to a Vax 780 / 750 / etc, and as modems and computers got faster it was still useful, but at today's network bandwidths and cpu speeds it's thunderous overkill.
https://news.ycombinator.com/item?id=38996713
A redisplay algorithm, by James Gosling (ACM SIGPLAN Notices, April 1981):
https://donhopkins.com/home/documents/EmacsRedisplayAlgorith...
>7. Acknowledgements: The people who did the real work behind this paper are Mike Kazar, Charles Liescrson and Craig Everhart; all from CMU.
>Bibliography: 1. Kevin Q. Brown. Dynamic Programming in Computer Science. CMU, February, 1979.
That code was also used in Maryland Windows (a text based overlapping/tiled window system developed at the University of Maryland by Chris Torek, like Emacs - Text Editor + Window System, kind of like "screen&qu...
We have an interpreted language in which you can call "subroutines" by name. But you can build the name in you program "on the fly", for example out of data.