A simple example for someone who wants to understand Dynamic Programming
AlgorithmDynamic ProgrammingAlgorithm Problem Overview
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.
Algorithm Solutions
Solution 1 - Algorithm
Check out this site: Dynamic Programming Practice Problems
Solution 2 - Algorithm
Here is a good tutorial comprising 29 solved DP problem with great explanation.
Solution 3 - Algorithm
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)
Note that each of the Code Jam practice contests has a "Contest Analysis" section for if you're stumped trying to solve the problem.
Solution 4 - Algorithm
- 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.
- If you want small tutorial videos on DP problems you can check this problem set from MIT.
Solution 5 - Algorithm
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.