Algorithm and data structure learning resources for dynamic programming

Question

Im learning dynamic programming now, and while I know the theory well, designing DP algorithms for new problems is still difficult.

This is what i would really like now- A book or a website, which poses a problem which can be solved by dynamic programming. Also there is the solution with an explanation available, which i would like to see if i cant solve the problem even after butting my head at it for a few hours. Is there some resource that provides this sort of a thing for several categories of algorithms- like graph algorithms, dynamic programming, etc?

P.S. I considered Topcoder, but the solutions there are not really appropriate for learning to implement efficient solutions.

Answer 1

Any of the ACM contest problem sets would probably work. Some places to find such:

• http://online-judge.uva.es/problemset/
• http://www.algorithmist.com/index.php/UVa%5FVolume%5FI

Answer 2

Many problems in Project Euler can be solved elegantly by using dynamic programming.

Answer 3

http://www.topcoder.com
Here you will find all types of questions of varying difficulty level.

Answer 4

I disagree somewhat that the solutions on TopCoder are not examples of good practice. The solutions submitted by the top users are often very simple and not necessarily extremely efficient, just efficient enough. What really matters is that the code is very short, which makes it a lot easier to understand, especially if you don't already know the solution.

I don't recommend writing ordinary programs in the same style, but it can definitely teach you something about over-engineering. I've seen solutions in Java with custom iterators, comparators, etc. and they were much harder to understand, even if the algorithm itself was trivial.

I once read an essay by Paul Graham, where he states that programs with fewer tokens are easier to understand. TopCoder has convinced me that this is true, at least in some domains.