A simple example for someone who wants to understa

问题:

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.

回答1:

Check out this site: Dynamic Programming Practice Problems

回答2:

Here is a good tutorial comprising 29 solved DP problem with great explanation.

回答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.

回答4:

1. Geeks for geeks has a great collection of dynamic programming problems. I feel this set is one of the best if you are preparing for interview.
2. If you want small tutorial videos on DP problems you can check this problem set from MIT.

回答5:

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_distance