3 ms·
Other popular examples he could consider adding: Image seam carving. Remember when this was all the rage a while ago? The 2D offset pattern is "up-left, up, up
by psykotic 16y ago
Other popular examples he could consider adding:
Image seam carving. Remember when this was all the rage a while ago? The 2D offset pattern is "up-left, up, up-right" for the vanilla version of the algorithm. If you want to support seams with a sharper slope, the offset pattern will be correspondingly wider.
Optimal game playing. Whenever the space of states is much smaller than the space of move sequences, you probably want dynamic programming. Example: The game state consists of a string of tokens, each with a point value. Players take turns removing a token from the string's left or right edge, adding its value to their running score. Here the move space grows exponentially but the state space only grows quadratically.
Pseudo-polynomial algorithms for NP-complete problems. You can think of these as one-player games analogous to the above two-player games where as before the state space has small size compared to the move space. A classic example is the knapsack problem with integer weights and a small knapsack; here the table offsets would be the different weights.
I've long loved this quote from Steve Skiena:
"Once you understand it, dynamic programming is probably the easiest algorithm design technique to apply in practice. In fact, I find that dynamic programming algorithms are often easier to reinvent than to try to look up in a book. That said, until you understand dynamic programming, it seems like magic."
When I first read this as a kid having a hard time grokking dynamic programming, I thought it was bluster. Now I know it's the absolute truth. You could even argue that dynamic programming should be considered a single algorithm rather than an algorithm design technique, but that might be going too far.
- jules 16y ago> "Once you understand it, dynamic programming is probably the easiest algorithm design technique to apply in practice. In fact, I find that dynamic programming algorithms are often easier to reinvent than to try to look up in a book. That said, until you understand dynamic programming, it seems like magic. This is especially true if you apply memoization to the naive recursive formulation to obtain an efficient algorithm. http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/memoize http://clojure.github.com/clojure/clojure.core-api.html#cloj...
- pjscott 16y agoWhen I first read about dynamic programming, I was already familiar with the idea of memoizing a naive recursive program to make it efficient. After that, hearing all this talk about oddly-shaped tables was actually kind of irritating. "Why are they going to all this trouble to talk about specific ways of memoizing recursive functions?" I asked myself, rhetorically. "Using a hash table has the same amortized asymptotic complexity, and this shouldn't be hard." It just seemed like way too much artificial complexity for what was, at heart, a remarkably simple and easy technique. This still bothers me. Perhaps it's a historical relic from the ancient times when dynamic programming was done by hand, and those oddly-shaped tables were needed to make it easier for the people working as computers.
- psykotic 16y agoMemoization and dynamic programming are not exactly the same. Memoization wins when the filled-in part of the table is expected to be sparse. Because dynamic programming works bottom up, it always fills in the entire table. Memoization's downside is that it uses a lot of memory. For the simple variant of the edit-distance problem it uses O(n^2) memory as opposed to O(n) memory with dynamic programming. In relation to this, the cache behavior and other constant factor overhead is usually much worse with memoization.