2 ms·
> "Once you understand it, dynamic programming is probably the easiest algorithm design technique to apply in practice. In fact, I find that dynamic programming
by 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.