This repository contains materials for a workshop on dynamic programming given at the Recurse Center on October 6, 2016. It includes source code for all examples discussed, the presentation document, and most importantly, a list of resources / tips in this readme.
In terms of learning the ideas and theory behind dynamic programming, I'd like to recommend the lectures in part 2 of the Stanford Algorithms course on Coursera. You can skip right to the dynamic programming lectures, they're in week 3. A lot of the materials for this workshop were drawn from these lectures so some things will be familiar.
Besides that, I'd recommend 2 things:
- Practicing lots of problems in the dynamic programming category on Leetcode
- Searching for other videos / explanations of some of the more "classic" DP algorithms. A couple I'd recommend learning about are:
- The Coin Change problem
- String edit distance (helps you solve a whole class of string matching problems, like RegEx matching, etc. I found this video and this video to be really helpful, both from a Coursera course on gene sequencing)
- The Knapsack problem (covered in the workshop)
- The Longest Common Subsequence algorithm
Here I've listed some of my favorite dynamic programming problems on leetcode (and a couple from Project Euler), ordered by difficulty.
These are pretty similar to the ones we did in workshop (with 1 dimension)
- Climbing stairs (similar to a problem covered in workshop)
- House robber (covered in workshop)
- Stock selling (a variant on classic DP principles)
- Max sum subarray (a little more difficult)
I tried to include some 2 dimensional problems here, as well as more complex string / sequence problems.
- Subsequence check (First introduction to string comparison dynamic programming)
- Longest wiggle subsequence (More sequence/subsequence practice)
- Min path sum (An introduction to (usually contrived) pathfinding DP problems)
- More pathfinding (Slightly harder pathfinding)
- Coin change (Another classic)
- Min perfect square sum (Good 2d problem)
An assortment of problems of the more difficult variety.
- More stock buying (A tough variation to the max profit problem)
- Count unique BSTs (No comment)
- Edit distance (Would recommend watching the videos listed above for this one. Maybe give it a shot though?)
- Wildcard / regex matching (Can be solved with dynamic programming, but I think there are more efficient non-DP solutions)
For any of these problems, I would highly recommend looking at the discussion forum on Leetcode once you've finished your solution. I've learned more from people on there than most other sources combined.