A simple example for someone who wants to understand Dynamic Programming

Question

I am looking for a manageably understandable example for someone who wants to learn Dynamic Programming. There are nice answers here about what is dynamic programming. The fibonacci sequence is a great example, but it is too small to scratch the surface. It looks a great subject to learn about although I haven't taken the algorithms class yet, hopefully it is on my list for the spring.

Thanks,

Answer 1

Calculating Levenshtein distances was one of the first problems I solved with dynamic programming; I think it is a decent next step from the Fibonacci sequence in terms of complexity.

http://en.wikipedia.org/wiki/Levenshtein%5Fdistance

Answer 2

Check out this site: Dynamic Programming Practice Problems

Answer 3

The idea behind dynamic programming is that you're caching (memoizing) solutions to subproblems, though I think there's more to it than that.

There are many Google Code Jam problems such that solutions require dynamic programming to be efficient. Examples:

Welcome to Code Jam (moderate)

Cheating a Boolean Tree (moderate)

PermRLE (hard)

Note that each of the Code Jam practice contests has a "Contest Analysis" section for if you're stumped trying to solve the problem.

Answer 4

TopCoder tutorial for DP is one of the best.