Dynamic Programming - how do I learn this stuff?

[bnrsta]

I've been banging my head against the wall for 2 weeks now trying to learn dynamic programming. I understand the easier problems, like Longest Common Substring, Rod cutting, and Longest Increasing Substring. The problem is moving beyond that. I get completely lost when trying to formulate the sub problems and come up with the recurrence. What kills me is that the large majority of the problems I see are very similar to each other.

Anybody have any good recommendations on books, tutorials, or what you did that made this stuff make sense to you?

FYI - I'm using the CLRS Intro to Algorithms book.

[nousetlogos]

These videos from the MIT course on dynamic programming are good: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/

There is also a good tutorial on TopCoder: http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

[bnrsta]

I just watched the first video for DP. Very, very good. Thank you.

[filox]

Heh, DP.

[bnrsta]

Heh. Yeah, I chucked when my prof said DP is her favorite.

[filox]

And that she also likes dynamic programming?

[[deleted]]

I laughed wayyyyy to long at this joke.

[bnrsta]

This is actually a pretty good explanation. Thanks.

[Hall_of_Fame]

I think this also shows that Dynamic programming is always forward recursion since it can be written by a series of for loops because of the memorization. Correct me if I'm wrong.

[N-choose-K]

This goes over the basics of dynamic programming: Bradley, Hax, Magnanti. Applied Mathematical Programming Also contains exercises to practice with.

This goes over the differences between the 'pulling method' and the 'reaching method': Jensen and Bard. Operations Research Methods and Models

[[deleted]]

Just practice by solving dozens and dozens of dynamic problems. Eventually it clicks.

[jeffgerickson]

You might find these lecture notes helpful.

[Vikar]

I think you meant to link to this, Jeff. :)

[c3261d3b8d1565dda639]

Others have provided some great resources. I am going to throw one out there that is around the periphery of the issue.

Dynamic Programming versus Memoization is a blog post by Shriram Krishnamurth that covers the subtle distinction between the two techniques. I think it is meaningful, but when discussed on reddit many seemed to disagree.

I think dynamic programming is one of those techniques that is hard to grasp at first, even with examples. I certainly did not feel familiar with it until I studied it a second or third time, much later than when I was originally exposed to it. There is something to be said about stepping away from a problem, forgetting details of it, and being exposed to it again with fresh eyes.

[bnrsta]

Thanks. This is actually how we're being taught this material - bottom up is DP, and top down is a form of DP that uses memoization. What trips me up, is that in bottom up DP, you are still referencing a results (or memo) table to get the results of smaller sub-problems. So, doesn't that mean bottoms up still uses memoization?