Dynamic Programming Book Recommendation?

Question

I've been trying to learn dynamic programming but it's been hard. The books and lecture videos I've come across so far usually talk about specific problems in dynamic programming but don't really enable me to grasp it. They're sort of like books that when introducing recursion, give examples of problems like towers of hanoi and printing permutations of a word. Useful reference but somehow lacking when you're trying to solve other problems that require recursion.

For me, the book that really taught me recursion was The Little Schemer. Brilliant book. So, I'm hoping to find a book like it that focuses on dynamic programming. Lot's of sample code and minimal explanation, giving me lots of practice. Any language is fine.

Answer 1

Cannot recommend a book, other than my algo class bible, but try solving Proj Euler Prob #15 using dynamic programming. It ought to help. To me there came a point in algo class when I think I "got it" - started to recognize when dynamic programming is applicable, and how to do it. Maybe I am too confident and have not seen super-hard examples yet, but I think I "got it". Good luck.

http://projecteuler.net/index.php?section=problems&id=15

Answer 2

I learned dynamic programming as part of a CS algorithm course. We used the book by Cormen et al. Chapter 15 deals with DP, and at the time I found it quite useful (combined with the lectures). But I just flipped through the book and doubt it meets your criteria: Only pseudo-code and lengthy explanations.

I see some contradiction in your statements: You complain that books focus on specific problems, but want one that has lots of sample code. And sample code means treating specific problems!

I am not familiar with any books with DP as the sole topic and I think there is no Little Schemer of DP. Probably because it is a less fundamental part of computer science. The most difficult part of DP is not the method itself, but finding out if it is applicable in your case: Does the problem have overlapping subproblems and what is its optimal substructure and cost function.

I found an online article on DP that gives a good introduction with some Python code. Perhaps this is a good start?