98

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.

Community
  • 1
  • 1
Khaled Alshaya
  • 94,250
  • 39
  • 176
  • 234

5 Answers5

30

Check out this site: Dynamic Programming Practice Problems

Nick Dandoulakis
  • 42,588
  • 16
  • 104
  • 136
  • 1
    Seeing this lecture from MIT http://video.mit.edu/watch/introduction-to-algorithms-lecture-19-dynamic-programming-i-fibonacci-shortest-paths-14225/ and then solving the above problems, would help you understand why DP is helpful. – pg2286 Oct 12 '16 at 11:33
  • Case in point the youtube link in the comment is already broken. New link: https://www.youtube.com/watch?v=OQ5jsbhAv_M – AJP Mar 17 '18 at 19:37
  • Check out this set of videos which I found it covers both top-down and bottom-up aspect of the algorithms pretty intuitively: https://www.youtube.com/playlist?list=PLx-Ye3Zw0WL0O_IDmbcVHlKqJuGEfw3VG – william007 May 14 '19 at 08:59
  • Looks like MIT moved their content from the main page to the MIT OpenCourseWare page, so the link @pg2286 provided is invalid. The link is now [19. Dynamic Programming I](https://youtu.be/OQ5jsbhAv_M) The full playlist [Introduction to Algorithms](https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb) is also available – rite2hhh Jul 29 '20 at 14:07
21

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

akashchandrakar
  • 2,009
  • 3
  • 23
  • 47
7

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.

Joey Adams
  • 41,996
  • 18
  • 86
  • 115
  • Thanks for the resources. I solve one or two questions from project euler from time to time, and it seems that I am really stuck at some problems which need knowledge about DP. – Khaled Alshaya Oct 08 '09 at 22:41
5
  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.
Diptendu
  • 2,120
  • 1
  • 15
  • 28
4

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

David Winslow
  • 8,472
  • 1
  • 31
  • 27