Timeline for Deciding on Sub-Problems for Dynamic Programming
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14, 2014 at 17:12 | comment | added | mrk | Strategy is clear, but how do you go about finding a recurrence? Is there a technique or just study lots of DP problems. | |
| Mar 23, 2012 at 20:19 | comment | added | Jules | Sorry for spamming this thread so much, but DFA minimization using this technique is just too lovely. Not many people realize that this is just dynamic programming, like many other algorithms. Here is a program for computing the equivalent states of a DFA in essentially 2 lines: pastebin.com/1cBtDdXz The same technique can also be used to handle left recursion in recursive descent parsers. And Hindley-Milner type inference of mutually recursive functions. And a Datalog interpreter. Etc, etc. Newton's method and infmemo pretty much make 95% of algorithms trivial. | |
| Mar 23, 2012 at 19:35 | comment | added | Jules | Here is a Python implementation: pastebin.com/AugVDvRA You just put @memo in front of your recursive algorithm and it will magically become a dynamic programming algorithm. | |
| Mar 23, 2012 at 19:26 | comment | added | Jules | Last but not least, this can have huge performance advantages. For example the traditional bottom up subset sum algorithm can compute tons of unneeded table entries. With this method only the necessary table entries will be computed. | |
| Mar 23, 2012 at 19:21 | comment | added | Jules | It's also possible to automatically turn a top-down recursive procedure into a dynamic programming algorithm. When you are about to return, store the answer in a hash table. On the start of each call, check if the answer is already in the hash table, and if so, return it immediately. Many algorithms become easy with this idea. For example with such a table, recursive algorithms on tries automatically work on DAWGs. By storing a sentinel value in the table at the start of a call, the same algorithms can work even on DFAs. Algorithms on BDDs become very easy to specify recursively. | |
| Mar 22, 2012 at 16:47 | comment | added | Suresh | My understanding of how to teach DPs is STRONGLY influenced by @JeffE's notes :) | |
| Mar 22, 2012 at 14:06 | comment | added | Dai | @JeffE Yes, I read and used your notes when teaching my algorithm classes and it was effective. Quote: "Dynamic is not about filling in tables. It's about smart recursion!" | |
| Mar 22, 2012 at 10:55 | vote | accept | daniel gratzer | ||
| Mar 22, 2012 at 9:35 | comment | added | JeffE | I claim that's the only strategy. | |
| Mar 22, 2012 at 4:36 | history | answered | Suresh | CC BY-SA 3.0 |