A simple example for someone who wants to understand Dynamic Programming [closed]

Closed. This ques开发者_如何学编程tion does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed 7 years ago.

Improve this 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.

---

Check out this site: Dynamic Programming Practice Problems

---

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

---

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.

---

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.

---

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