11 ms·
“Dynamic programming” is not referring to “computer programming”
- teleforce 1y agoFun facts the venerable Border Gateway Protocol or BGP is using distant-vector algorithm for global Internet routing calculation based on Bellman-Ford dynamic programming approach due to its scability in updating the routing table [1]. For intranet routing however shortest path algorithm based on Dijkstra approach underlies the OSPF and IS-IS protocols. In the old days distant-vector protocol like Routing Information Protocol protocol or RIP is also used but it's now becoming obsolete and humorously known as Rest In Peace protocol. Distant-vector now is making a comeback for intranet in the form of mobile ad hoc and mesh networks (guerilla networks for routing without infrastructure) with Ad hoc On-Demand Distance Vector Routing protovol or AODV [2]. This setup can be very beneficial for disaster and also for mobile group or platoon communication. [1] Distance-vector routing protocol: https://en.wikipedia.org/wiki/Distance-vector_routing_protocol https://en.wikipedia.org/wiki/Distance-vector_routing_protoc... [2] Ad hoc On-Demand Distance Vector Routing: https://en.wikipedia.org/wiki/Ad_hoc_On-Demand_Distance_Vector_Routing https://en.wikipedia.org/wiki/Ad_hoc_On-Demand_Distance_Vect...
- smokel 1y agoAlso, the term "dynamic programming" has slightly different meanings in the context of leetcode problems and in the context of reinforcement learning. In the first it's for optimizing a relatively small deterministic system, in the latter it is for optimizing a stochastic process. Pretty confusing.
- jeltz 1y agoThe idea is way older than both leetcode and reinforcement learning and is used everywhere (for example when planning SQL queries). If reinforcement learning invented a new way to use the word then that is all their fault because leetcode is true to the original meaning.
- smokel 1y agoBoth meanings derive from Bellman. "Reinforcement learning" did not invent a new way, and the field of reinforcement learning predates leetcode by a large margin.
- jeltz 1y agoSo what is the confusion then? Leetcode got it from real computer science and engineering and retained the original meaning in both steps without any changes. Every bigger piece of software you use probably uses dynamic programming somewhere. Or do you think that e.g. PostgreSQL is leetcode? There is nothing derived here. It is exactly the same meaning.
- smokel 1y agoPerhaps we misunderstand each other. I'm saying that the mathematical optimization method differs from the algorithmic paradigm, as explained on this Wikipedia page for example: https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming. That is to say, they serve different purposes and are distinct concepts. They sure have the same fundamental basis laid out by Bellman, but the applications have diverged quite a bit. Do you mean to say that these two concepts also have exactly the same meaning?
- mrbluecoat 1y agoReminds me of "Extreme Programming" [0], which is referring to project programming rather than computer programming. [0] https://en.m.wikipedia.org/wiki/Extreme_programming https://en.m.wikipedia.org/wiki/Extreme_programming
- rzzzt 1y agoCompare with "Extreme Ironing": https://www.ebaumsworld.com/pictures/23-insane-examples-of-extreme-ironing/84419797/ https://www.ebaumsworld.com/pictures/23-insane-examples-of-e...
- userbinator 1y agoIf it weren't for the fact that the page is 10 years old, I would've thought those were AI-generated images at first glance.
- stephenlf 1y agoI love that origin story.
- gsf_emergency_2 1y agoIt 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 https://cs.stackexchange.com/questions/99513/dynamic-programming-vs-memoization 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"
- LPisGood 1y agoYou should think of the “programming” in dynamic programming the same way you think of in linear programming, integer programming, and constraint programming. Indeed even in layman’s terms, thinking of it as in television programming is more accurate than thinking it is related to computer programming (as is mentioned in TFA)
- TeMPOraL 1y ago> linear programming, integer programming, and constraint programming Can't think of a universe in which you'd learn about these things before learning "computer programming".
- tgma 1y agoThere was a universe before digital computers were popular or a thing at all. Computing predates computers.
- Thorrez 1y agoBefore digital computers existed, there were still computers. They were people. A baker is a person who bakes. A computer was a person who computes (computing mathematical results).
- npsomaratna 1y agoSri 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.
- deaddodo 1y agoTechnically, "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.
- zekica 1y agoI had the same experience: no one knew of my mentors what "dynamic programming" was and our country-level competition (that had created problems inspired by IOI) required dynamic programming for 2 out of 5 problems. And of course I failed the first time (2004). Then I learned what it was about and aced the next time (2005).
- snthpy 1y agoI was part of the hosting team at IOI 1997 in Cape Town and had similar conversations with the participants that you described and also learned about Dynamic Programming there. Your description of it as "recursion + storing results which you can sometimes do iteratively" is the best summary. Good example is iterative Fibonacci algorithm. Another fun anecdote from that time is that we had to take special precautions with the scoring program which connected to the participants machine over the serial port. The previous year one participant had hacked the serial port interface to manipulate the results. :-)
- ygritte 1y ago> Try thinking of some combination that will possibly give [the word, dynamic] a pejorative meaning. It’s impossible*. > *This Haskell fan’s contender is “dynamic typing” :P Nothing is impossible!
- zoky 1y agoIt’s certainly possible to use it as a euphemism, if not an outright pejorative. “Dynamic truthfulness”, “dynamic sense of morality”, etc.
- eru 1y agoThere's also dynamic scoping; as opposed to lexical scoping a.k.a. static scoping. You can find defenders of dynamic typing, but dynamic scope is now widely seen as a mistake. Or at least dynamic scope by default; it has specialised uses--and in Haskell the Reader Monad is basically isomorphic to dynamic scoping and no one complains about it.
- ygritte 1y ago> dynamic scoping Right you are. Even more horrible. The tcl language still has it!
- School-Cotton 1y agoSo does emacs lisp, by default, although you can set it to lexical scope per-file (and it’s recommended to always do so).
- eru 1y agoI think EmacsLisp also does dynamic scoping. Or at least they used to about ten years ago. Not sure, if they fixed it?
- jrapdx3 1y agoWell, Tcl is kind of a mixture of scope rules. In some respects, e.g., within a proc, it's mainly a lexical environment, but of course dynamic scoping is introduced by commands like upvar/uplevel. FWIW Tcl programmers don't concern themselves very much with sorting out dynamic vs. lexical. In any case, Tcl programmers are careful to maximize static scoping. No doubt that's necessary to create reliable larger programs many of which have been written in Tcl.
- commandersaki 1y agoSame for "linear programming".
- marcosdumay 1y agoThe "linear" in linear programming at least is related to the problem it's solving (linear optimization).
- IshKebab 1y agoPossibly 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. I prefer "cached recursion".
- eru 1y agoWell, cached recursion is a bit too generic. Almost anything can be done with both caches and recursion. We had a different characterisation in one of our mathematical optimisation classes: dynamic programming is basically every problem that isomorphic to finding the longest path in a graph, with suitable 'overloading' of 'maximum' (for picking among multiple alternative paths) and 'addition' (for combining multiple sub-paths). First, to illustrate what I mean by this overloading: matrix multiplication usually has multiplication () and addition (+). However, in the min-plus-algebra you overload (+) with minimum and () with plus, and then multiplying matrices becomes equivalent to hopping two paths in the adjacency matrix of a graph. (Sorry, if this is a bit confusing.) Specifically, taking an adjacency matrix A and calculating A* := 1 + A + AA + AAA + ... is equivalent to taking the transitive closure of edge hopping in your graph, ie the shortest paths between all pairs of vertices. If you overload (+) with maximum and () with plus instead, you can find longest paths. For that to make sense, you should not have cycles in your graph. Now let's go back to dynamic programming: the shared optimal sub-structure property of dynamic programming is exactly the same as what you have in finding longest paths. The structure might sound overly restrictive, but you'll find that it works for all (most?) examples of dynamic programming. P.S. My recollection was a bit vague, so I asked ChatGPT for some help, and apparently I wasn't completely wrong: https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c10b https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c1... P.P.S. Despite everything I said above, I agree that 'cached recursion' is still a better name than dynamic programming.
- tgma 1y agoI actually think overly focusing on the memoized recursion undermines the core conception of dynamic programming. Remember, as noted in the post, the term programming refers to a tabular method of planning, i.e. specifically, the bottom-up calculation to solve a problem. The emphasis here is on a predetermined order on how to tabulate the plan to get to the desired result which will be the solution to the broader problem. The memoized recursive function is an implementation methodology on a digital computer that specifically side-steps the question of in which order one should do the tabulation. I would argue that recursive memoization is a possible solution technique to dynamic programming problems (defined as the universe of problems that admit a dynamic programming solution,) but strictly speaking, in and of itself, is not dynamic programming.
- tgma 1y agoProgramming 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."
- random3 1y agoI can't find the resource, but, according to Bellman he needed a name that wouldn't sound like something the army would scrape— effectively protecting his research. He had a few options and "dynamic" sounded "cool" enough, in his opinion, for army. This said, the "programming" part is pretty accurate, but IMO the author misses the point with what "computer programming" meaning is, afterall.
- mr_toad 1y agoLinear programming gets confused with programming, but also with linear algebra and linear modelling.
- nextaccountic 1y agoProgramming in this sense means just optimization
- bob1029 1y agoDynamic 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.
- lblume 1y agoDynamic optimality sounds like a very euphemistic description of Levin's Universal Search to me – it is definitely optimal, just in a very, hmm, dynamic, let's say, way.
- sureglymop 1y agoI 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!
- eric-burel 1y agoThe article would probably be more complete with references to similar terms "linear program" or "integer program", unless this is also a slightly different meaning?
- pss314 1y agoRichard Bellman on the Birth of Dynamic Programming (2002) [pdf] https://news.ycombinator.com/item?id=42482289 https://news.ycombinator.com/item?id=42482289
- nottorp 1y ago> 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.
- lblume 1y agoI thought communist nations heavily relied on programs (in the author's sense) for their planned economies?
- nottorp 1y agoNo, on "plans". Mostly five year plans. At least in Romanian. The only other use of "program" I remember from back then is "tv program".
- lblume 1y agoAccording to [1], the optimization done in the Soviet Union (the largest planned economy) was based on linear programming. [1]: https://www.rtsg.media/p/soviet-planning-demystified https://www.rtsg.media/p/soviet-planning-demystified
- nottorp 1y agoBut this subthread is not about what they were using but about localized names for computer programming vs other forms of programming. Also I don't think Soviet examples help because I don't think the last few soviet dictators before the iron curtain's fall were against computers, while Ceausescu definitely was.
- sigmoid10 1y agoLooks 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. [1] https://www.reddit.com/r/learnprogramming/comments/1ac9zbl/dynamic_programming_what_is_it_exactly_for_me_its/ https://www.reddit.com/r/learnprogramming/comments/1ac9zbl/d...
- globular-toast 1y agoHuh, I've never realised this. It actually makes more sense if I revert to my native British spelling of programme in this sense. A program can use dynamic programming to dynamically figure out the programme required to perform a computation.
- cousin_it 1y agoMy 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.
- julien6arzola 1y ago[flagged]
- DonHopkins 1y agoJames Gosling's infamous Emacs screen redisplay algorithm uses dynamic programming. https://en.wikipedia.org/wiki/Gosling_Emacs 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 M[i,j] = MIN (M[i-1,j]+dcost, # UP, implies delete M[i,j-1]+icost+redraw cost, # LEFT, implies ins+redraw M[i-1,j-1]+rewrite cost) # BACK, implies rewrite 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-stallman-answers-your-questions 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_originally_written_by_james_gosling/ 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 https://news.ycombinator.com/item?id=38996713 A redisplay algorithm, by James Gosling (ACM SIGPLAN Notices, April 1981): https://donhopkins.com/home/documents/EmacsRedisplayAlgorithm.pdf 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" or "mux" or "mgr"). https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Dynamic_programming https://wiki.c2.com/?DynamicProgramming https://wiki.c2.com/?DynamicProgramming https://en.wikipedia.org/wiki/ManaGeR https://en.wikipedia.org/wiki/ManaGeR https://news.ycombinator.com/item?id=22849522 https://news.ycombinator.com/item?id=22849522 >Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art, warning any would-be improver that even if they thought they understood how the display code worked, they probably did not. https://donhopkins.com/home/archive/emacs/mw/display.c https://donhopkins.com/home/archive/emacs/mw/display.c /* 1 2 3 4 .... Each Mij represents the minumum cost of +---+---+---+---+----- rearranging the first i lines to map onto 1 | | | | | the first j lines (the j direction +---+---+---+---+----- represents the desired contents of a line, 2 | | \| ^ | | i the current contents). The algorithm +---+---\-|-+---+----- used is a dynamic programming one, where 3 | | <-+Mij| | M[i,j] = min( M[i-1,j], +---+---+---+---+----- M[i,j-1]+redraw cost for j,2 4 | | | | | M[i-1,j-1]+the cost of +---+---+---+---+----- converting line i to line j); . | | | | | Line i can be converted to line j by either . just drawing j, or if they match, by moving . line i to line j (with insert/delete line) */ Trivia: That "Skull and Crossbones" ASCII art is originally from Brian Reid's Scribe program, and is not copyrighted. https://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt https://donhopkins.com/home/archive/emacs/skull-and-crossbon... /-------------\ / \ / \ / \ | XXXX XXXX | | XXXX XXXX | | XXX XXX | \ X / --\ XXX /-- | | XXX | | | | | | | I I I I I I I | | I I I I I I | \ / -- -- \-------/ XXX XXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXXXXXX XXXXX XXXXX XXXXXXXXX XXXXXXXXXX XXXXX XXXXX XXX XXX ************** * BEWARE!! * ************** All ye who enter here: Most of the code in this module is twisted beyond belief! Tread carefully. If you think you understand it, You Don't, So Look Again. But if you're not trying to support old terminals (but might still have a slow "thin wire" network connection), there is an orders of magnitude better approach: The Emacs NeWS display driver (for both UniPress and Gnu Emacs) downloaded PostScript code to define an efficient application specific network protocol with instantaneous local input tracking and feedback (unlike how X-Windows uses a fixed protocol, but like how AJAX uses JavaScript). The source code to Gosling's UniPress Emacs 2.20 just recently surfaced, and the display code is well commented (still including the skull and crossbones and ascii art diagrams): https://github.com/SimHacker/NeMACS/blob/main/src/DspVScreen.c https://github.com/SimHacker/NeMACS/blob/main/src/DspVScreen... And the lower level terminal driver layer: https://github.com/SimHacker/NeMACS/blob/main/src/DspTrm.c https://github.com/SimHacker/NeMACS/blob/main/src/DspTrm.c The NeWS terminal drivers I worked on for UniPress and Gnu Emacs were layered on top of that dynamic programming screen update code. But instead of sending escape codes to a dumb terminal, it downloaded PostScript code into the NeWS server to implement drawing, mouse tracking, text selection feedback, pie menus, tabbed windows, etc, and sent binary PostScript tokens back and forth (a practice now called "AJAX" for X = XML or JSON text instead of binary PostScript data and code): TrmPS.c: https://github.com/SimHacker/NeMACS/blob/main/src/D.term/TrmPS.c https://github.com/SimHacker/NeMACS/blob/main/src/D.term/Trm... TrmPS.cps: https://github.com/SimHacker/NeMACS/blob/main/src/D.term/TrmPS.cps https://github.com/SimHacker/NeMACS/blob/main/src/D.term/Trm... PostScript stuff for Emacs: https://github.com/SimHacker/NeMACS/tree/main/ps https://github.com/SimHacker/NeMACS/tree/main/ps Emacs 2.20 Demo (NeWS, multiple frames, tabbed windows, pie menus, hypermedia authoring): https://www.youtube.com/watch?v=hhmU2B79EDU https://www.youtube.com/watch?v=hhmU2B79EDU Here's a brochure from February 1988 about UniPress Emacs 2.20 and "SoftWire" (NeWS without graphics, kind of like Node with PostScript instead of JavaScript). What is Emacs: https://www.donhopkins.com/home/ties/scans/WhatIsEmacs.pdf https://www.donhopkins.com/home/ties/scans/WhatIsEmacs.pdf I also worked on the Gnu Emacs 18 NeWS display driver (supporting a single tabbed windows and pie menus in The NeWS Toolkit 2.0): tnt.ps: https://www.donhopkins.com/home/code/emacs18/src/tnt.ps https://www.donhopkins.com/home/code/emacs18/src/tnt.ps tnt.cps: https://www.donhopkins.com/home/code/emacs18/src/tnt_cps.cps https://www.donhopkins.com/home/code/emacs18/src/tnt_cps.cps tnt.c: https://www.donhopkins.com/home/code/emacs18/src/tnt.c https://www.donhopkins.com/home/code/emacs18/src/tnt.c tnt-win.el: https://www.donhopkins.com/home/code/emacs18/lisp/term/tnt-win.el https://www.donhopkins.com/home/code/emacs18/lisp/term/tnt-w... More on the NeWS versions of Emacs with links to code here: https://news.ycombinator.com/item?id=26113192 https://news.ycombinator.com/item?id=26113192
- amelius 1y agoWhat would we call it if it were invented today?
- GuB-42 1y agoProbably AI something. The name "dynamic programming" was chosen to impress bureaucrats, and AI is where it is at today. "Subtask training" maybe, as the idea is to train the algorithm on smaller tasks to to make it more efficient at solving larger tasks. Ok, it is just storing intermediate results, but it sounds more AI-ish like that.
- inopinatus 1y agoPartial/Intermediate Solution Storage
- amelius 1y agoTabularized memoization? Bottom-up memoization? Iterative memoization?
- cubefox 1y agoI thought both recursive top-down memoization and iterative bottom-up tabulation are considered instances of "dynamic programming".
- qprofyeh 1y agoThanks 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.
- butan-2-ol 1y ago[flagged]
- montebicyclelo 1y agoI always found that badly named things did make learning harder / more jarring; especially if an explanation for the incongruous name wasn't provided.
- layer8 1y agoSimilar for “linear optimization”, which doesn’t refer to program optimization.
- omnibrain 1y agoOk, but how do you call what we are doing: 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.
- throwawayffffas 1y agoDynamic programming is a subfield of mathematical programming. The field of studying optimization problems. It's called programming because programming means scheduling. And most of the problems the field initially concerned itself with were logistics scheduling problems. Computer programming is called programming because it involves scheduling instructions.
- zero_shift 1y agoI did not know that. Fascinating.
- throwawayffffas 1y agoFor all the people looking for different terminology, the word you are looking for is optimization. Dynamic optimization makes just as much sense. Same as Mathematical optimization does for the wider field of study.
- m3nu 1y agoIn strength training 'programming' means the details of your workout plan. Like how many sets, reps and exercises.
- ChrisMarshallNY 1y agoThat's a really interesting origin story. I had no idea, but I also totally believe it. I've seen things, man...
- graycat 1y agoYup: And stochastic dynamic programming and stochastic optimal control! Suppose a cargo plane is to fly from Kansas City to St. Louis, Chicago, Indianapolis, Dayton, Nashville, and Memphis and at each city pickup cargo. Suppose the cargo weights are known only in probability distribution from history and otherwise are probabilistically independent. Have weather reports for the winds and temperatures, but the actual values can vary from the reports. And suppose the fuel prices vary significantly among the stops but are known. Then, how much fuel should the pilot buy at each stop to minimize expected cost for the trip? I.e., in simple terms, buy extra fuel where it's cheap and carry (tanker) it to where it's expensive but in so doing burn extra fuel from the extra weight of the extra fuel. Solution: Stochastic dynamic programming. Hint: In Canada, the solution is illegal! Was meeting with Nemhauser (see references below); my cab back to the airport was waiting; and he gave me a 15 second lecture. On the plane thought about his lecture, ..., and stood for my Ph.D. orals and passed (extra credit for guessing my employer). Some references (with TeX markup): Stuart E.\ Dreyfus and Averill M.\ Law, {\it The Art and Theory of Dynamic Programming,\/} ISBN 0-12-221860-4, Academic Press, New York.\ \ Dimitri P.\ Bertsekas, {\it Dynamic Programming: Deterministic and Stochastic Models,\/} ISBN 0-13-221581-0, Prentice-Hall.\ \ George L.\ Nemhauser, {\it Dynamic Programming,\/} ISBN 0-471-63150-7, John Wiley and Sons, New York\ \ E.\ B.\ Dynkin and A.\ A.\ Yushkevich, {\it Controlled Markov Processes,\/} ISBN 0-387-90387-9, Springer-Verlag, Berlin.\ \ Wendell H.\ Fleming and Raymond W.\ Rishel, {\it Deterministic and Stochastic Optimal Control,\/} ISBN 0-387-90155-8, Springer-Verlag, Berlin.\ \ Michael Athans and Peter L.\ Falb, {\it Optimal Control:\ \ An Introduction to the Theory and Its Applications,\/} McGraw-Hill Book Company, New York.\ \ Dimitri P.\ Bertsekas and Steven E.\ Shreve, {\it Stochastic Optimal Control: The Discrete Time Case,\/} ISBN 0-12-093260-1, Academic Press, New York.\ \ E.\ B.\ Lee and L.\ Markus, {\it Foundations of Optimal Control Theory,\/} ISBN 0471-52263-5, John Wiley, New York,
- cjfd 1y agoJust call it caching. The whole concept is a bit too simple to be a word.
- monkeyelite 1y agoThat thought comes from a programmer perspective. What’s interesting in terms of the theoretical properties and classification of a problem is the recursive nature with overlapping recursion.
- Jtsummers 1y agoIt doesn't require caching, though. So that's a wrong description of the concept.
- NoThisIsMe 1y agoYou're thinking of memoization, which is related to but distinct from DP. Memoization is "top down", DP is "bottom up". DP generally has better space complexity (memory requirements). For example, for a function that computers the Fibonacci sequence, space complexity with memoization is O(n), vs O(1) with DP. https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence https://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_...
- duped 1y agoFibonacci is a bad example because it relies on the linearity of `prev + current` to be O(1) memory complexity. A lot of divide-and-conquer schemes exploit symmetry and linearity of their internals but if the operation is nonlinear then it requires memoization/caching. On that note, I really struggle to understand what's special about "bottom up" versus "top down" DP or what categorizes it as unique from any other algorithms.
- Jtsummers 1y agoBottom-up solutions to DP problems allow you, if the structure permits, to throw away parts of the full table. This is more memory efficient. Or, you could build the table bottom-up which avoids the repeated verification step in memoized, top-down solutions because when you reach an entry that isn't filled, you know that its related subproblems have already been computed and cached. Someone posted an Euler problem with finding the maximal sum along any path (binary choice at each step) down a pyramid. The bottom-up solution only ever generates a "cache" of row elements (starting the row count from 1). The 100th row has 100 elements. When you go up to the 99th row you only need 99 elements by the end of calculating it, and so on. This is more efficient in memory than the n*(n+1)/2 (approx.) elements you'd need doing a top-down recursive, memoized version. Though in that case it's not awful on modern computers, it is a consideration for complex and large problems. The bottom-up version also lends itself to not needing to bring the entire pyramid into memory, only one row + the cache at a time so you only have |row| + |row| + 1 items in memory at any given time (plus some temp variables or index variables). Again, it can be very memory efficient. Technically, you don't even need the entire current row in memory, only one element of it and then read each new element as you step across the row which further reduces the memory overhead. With regard to building a full table, I realize Fib is a poor example in general but it is illustrative and fits in a comment. Let's say you memoize the naive version, then you have to include this check either before the recursive calls or at the start of each call: if n in FIB: # either return if at top of the function, or retrieve rather than make the recursive call This is unneeded if you build the table bottom-up: def fib_bottom_up(n): FIB = {1: 0, 2: 1} i = 3 while i <= n: FIB[i] = FIB[i - 1] + FIB[i - 2] return FIB Bottom-up construction of the table skips those checks which can add up for larger table constructions, or if you're building up many different tables. Consider a more complex optimization problem where different initial parameters result in different tables being generated (but by the same method). This bottom-up approach will be more efficient than the top-down approach. Of course, a benefit for top-down is when an input only needs some subset of the table. If the generated table will be sparse, but may not be easily constructed in a sparse manner bottom-up, then top-down can be better.
- manoji 1y agoDP(Dynamic Programming) is such a beautiful technique .It took a while for me to grasp it . There are many applications in real world systems as well. Eg Duck DB's join order optimizer is built on https://15721.courses.cs.cmu.edu/spring2020/papers/20-optimizer2/p539-moerkotte.pdf https://15721.courses.cs.cmu.edu/spring2020/papers/20-optimi... . https://github.com/duckdb/duckdb/blob/61f07c3221e01674d8fe40b4a25364ba2f3159a7/src/optimizer/join_order/plan_enumerator.cpp#L469 https://github.com/duckdb/duckdb/blob/61f07c3221e01674d8fe40...
- aldousd666 1y agoI learned what 'dynamic programming' was from studying the 'BLAST' algorithm for DNA sequence search. BLAST is a heuristic approximation for the otherwise Dynamic Programming algorithm created by 'Smith & Waterman' Before that, I would have misunderstood the term too.
- dang 1y agoMany past related threads, but these seem to be the interesting ones. Other interesting ones? Richard Bellman on the Birth of Dynamic Programming (2002) [pdf] - https://news.ycombinator.com/item?id=42482289 https://news.ycombinator.com/item?id=42482289 - Dec 2024 (9 comments) Dynamic programming is not black magic - https://news.ycombinator.com/item?id=38988948 https://news.ycombinator.com/item?id=38988948 - Jan 2024 (202 comments) Dynamic Programming vs. Divide-and-Conquer (2018) - https://news.ycombinator.com/item?id=26930667 https://news.ycombinator.com/item?id=26930667 - April 2021 (115 comments) Real-world dynamic programming: seam carving - https://news.ycombinator.com/item?id=20285242 https://news.ycombinator.com/item?id=20285242 - June 2019 (66 comments) Graphical Introduction to Dynamic Programming - https://news.ycombinator.com/item?id=19682258 https://news.ycombinator.com/item?id=19682258 - April 2019 (11 comments) Dynamic Programming for Technical Interviews - https://news.ycombinator.com/item?id=19395578 https://news.ycombinator.com/item?id=19395578 - March 2019 (218 comments) Solving dynamic programming interview problems - https://news.ycombinator.com/item?id=17102604 https://news.ycombinator.com/item?id=17102604 - May 2018 (164 comments) Dynamic Progamming: First Principles - https://news.ycombinator.com/item?id=15545686 https://news.ycombinator.com/item?id=15545686 - Oct 2017 (98 comments) What is difference between memoization and dynamic programming? - https://news.ycombinator.com/item?id=13281884 https://news.ycombinator.com/item?id=13281884 - Dec 2016 (1 comment) Dynamic Programming: The Name (1984) - https://news.ycombinator.com/item?id=12476597 https://news.ycombinator.com/item?id=12476597 - Sept 2016 (61 comments) Fibonacci series and Dynamic programming - https://news.ycombinator.com/item?id=5893237 https://news.ycombinator.com/item?id=5893237 - June 2013 (28 comments) Dynamic Programming versus Memoization - https://news.ycombinator.com/item?id=4434671 https://news.ycombinator.com/item?id=4434671 - Aug 2012 (26 comments) Visualizing dynamic programming - https://news.ycombinator.com/item?id=2243297 https://news.ycombinator.com/item?id=2243297 - Feb 2011 (11 comments) Ask HN: Have you ever used Dynamic programming in your dev job? - https://news.ycombinator.com/item?id=1796861 https://news.ycombinator.com/item?id=1796861 - Oct 2010 (11 comments) Why the name "dynamic programming"? - https://news.ycombinator.com/item?id=1290397 https://news.ycombinator.com/item?id=1290397 - April 2010 (25 comments) The Edit Distance Problem - https://news.ycombinator.com/item?id=571570 https://news.ycombinator.com/item?id=571570 - April 2009 (13 comments) Introduction to Dynamic Programming - https://news.ycombinator.com/item?id=329953 https://news.ycombinator.com/item?id=329953 - Oct 2008 (12 comments)
- AndrewKemendo 1y agoIf you haven’t, everyone should read Eye of the Storm It’s Bellmans autobiography and it’s very good though he doesn’t go as much into depth as I wanted on how he came up with DP and his inequality
- andreygrehov 1y agoIf anyone's interested, I published a short, ad-free YouTube series on Dynamic Programming about 4-5 years ago [1]. I haven't had a chance to continue it, but many people have found the course eye-opening. [1] https://www.youtube.com/@andreygrehov https://www.youtube.com/@andreygrehov
- an0malous 1y agoI read the post and all these comments and I still have no idea what dynamic programming is. I’m also slightly infuriated by the rationalization for the name mentioned in the post.
- stockresearcher 1y agoI've seen this many times before and it always presents Charles Wilson's aversion to "research" in a "haha what a luddite" manner. You have to understand that Eisenhower believed that the military industrial complex was out of control. He brought Wilson in to help rein it in and reorganize the defense department. The military and military contractors were conducting "research" in the form of doing chemical and biological weapons experimentation on soldiers and civilians without their knowledge or consent. Wilson was trying to stop that. And of course many of the think tanks were trying to lead the United States into an offensive war against the Soviet Union, which Wilson and Eisenhower did not want or think was necessary. It's entirely probable that the only reason Bellman got funding to do this work at RAND was because they intended to use it for running their desired war.
- ajuc 1y agoTop 3 worst name ever (along with "toxic masculinity" and "oxygen").