Dynamic Programming.

[Cinjection]

Hey guys.

I wrote CCC last year and breezed through the first 4 question and was absolutely stumped by the last one. I later found out, after some googleing, that the solution require a technique called dynamic programming, which I had never heard of before that day.

This year's CCC is coming up and I want to be ready for the DP question. I've read a couple online tutorials and learn theory about some of the concepts (like memoization, optimum substructure, and overlapping subproblems), but I'm still misty on the whole business. I want to see some examples of the thing in action. I wasn't too happy with the tutorials I found from googeling.

So my questions for you guys is, what tutorial did you use to learn DP? If you could forward me a link, I would be much obliged.1

[Tony]

Saad wrote a tutorial on dynamic programming, don't know if you've seen it already.

I don't think I ever formally covered dynamic programming. The concepts come naturally from using dynamic (dynamically typed?) languages like Ruby or Python.

[Saad]

Also I would recommend the book Introduction to Algorithms, its a really good book covering a wide area of algorithms including Dynamic Programming, and also Here is a good resource for problems, They give you bunch of problems and go over solutions to the problems.

[Cinjection]

Saad @ Sat Feb 02, 2008 3:16 pm wrote:

Also I would recommend the book Introduction to Algorithms, its a really good book covering a wide area of algorithms including Dynamic Programming, and also Here is a good resource for problems, They give you bunch of problems and go over solutions to the problems.

I'll give your tutorial a read.

Thanks guys.