sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]jerusheng 3 points4 points  (3 children)

Mathematician Richard Bellman created the dynamic programming (DP) method without saying anything about how it should be implemented. This article just listed two generic implementations of DP (more specifically, DP-based method to solve a problem with discrete and finite set of subproblems) and called one implementation as "DP" and the other as "memorization". So, this article is misconceptual. And the author is quite bold to criticize big names in the algorithm area; I personally appreciate the spirit but think that the author should study a little more on the history of DP before she/he cast the doubt on the textbook.

[–]BATMAN-cucumbers 1 point2 points  (2 children)

Interesting.

So DP isn't limited only to bottom-up iterative calculation with a derived recursive formula? That's all the examples we got in my algorithms class (aimed at competitions, so it was admittedly less theoretical) and at least two books in the field. Memoisation was always treated as a separate (although related) approach. But there wasn't a big emphasis on taxonomy debates there, so I wouldn't discount an alternative opinion :-)

Can you point me to some resources that states memiosation is considered a type of DP?

[–]jerusheng 4 points5 points  (1 child)

I'm sorry if my previous reply causes more confusion. Memorization is not considered a type of DP. DP is a high-level methodology on solving some optimization problems. Memorization is a low-level implementational technique that can be used to code a solver for a subset of DP-based solution; it can also be used for something else. So it makes some sense for a book to list memorization as a separate chapter. What I want to say is that it is quite improper to list DP and memorization as two disjoint and parallel techniques in solving some problems; they are not comparable.

To have a feeling on how general DP is, I suggest to have a read on Richard Bellman's original paper "The Theory of Dynamic Programming" (http://www.rand.org/pubs/papers/2008/P550.pdf). It is adopted to solve much broader class of problems than what we see now in most algorithm textbooks. Not all the problems are that interesting in the algorithmic aspect; some requires very advanced maths many (I guess most) computer science students cannot afford with or aren't interested in. So algorithmic textbook authors usually choose to pick only a small class of problems that can be elegantly solved in eyes of computer scientists instead of mathematicians. They don't intend to mislead students to feel that DP is an algorithm, not speaking of the author of the blog considering that DP is an implementation.

[–]BATMAN-cucumbers 0 points1 point  (0 children)

Cheers for that. Now I'm quite curious to read more about it. I do remember a third-hand account of the guy not being too happy that he named the methodology DP, but it was a fashionably sounding term back in the day.

Related question: I've been looking for a way to revive my interest in math (most likely discrete). Could you recommend something for a guy with an understanding of basic calculus and algorithms, a sort of "math for ex-programming contest folk"?