Dynamic programming practice problems with solutions

Question

Hi,

I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is there a website or book that contains practice problems and solutions?

Thanks
Bala

Answer 1

CLR, Introduction to Algorithms is considered one authoritative texts for algorithms. It's where I learned about dynamic programming.

Obviously, Wikipedia contains some good illustrative examples as well.

Answer 2

The best way to go about this is to start solving problems on:

• Topcoder
• ACM
• Spoj
• CodeChef

and read the discussions made by to programmers on their respective discussion forums. Top coder also has some very good DP tutorials.

Answer 3

There are quite a few problems on Project Euler which can be solved by dynamic programming, though you'll have to find out which problems by yourself. Also beware that they can be very hard.

A discussion of the solution becomes accessible once you've solved a problem.

Answer 4

You can find spoj problems that involve dynamic programming here