The best resource I've used for learning dynamic programming and actually having it click is the DP lectures from the OMSCS Graduate Algorithms course.
I'm definitely a fan of structured education. After all, what I learned about DP I learned from a fantastic college course. Glad to hear there are online resources for people to get that kind of education, so thanks for sharing!
Hopefully, an article like mine can help those who are not able invest in more lengthy study, or just need an additional perspective.
This article is fantastic, thanks so much. I kid you not, I was already planning to learn about DP tonight and then I saw this article and I'm done! I get it.
The tricky part to learn, and one that I'm sure comes with experience, is how to identify the subproblem + recurrence relation. One thing this clarified for me is the construction of the grid and how it is dependent on inputs because of the DAG. But you can have a recurrence relation that uses more than two sub-problems. i.e. the DP method for calculating Levenshtein distance involves a recurrence relation with 3 previous values (subtraction, addition, substitution).
You're absolutely right about figuring out the subproblems and the recurrence relation. I've found that knowing how you're going to use the recurrence relation is a first step to coming up with the right relation. For example, knowing you'll cache the results in a table means you're on the lookout for a function that has integer inputs, because you want the values to be indexed and ordered.
After that, as you said, practice is key. I'm working on a follow-up article that'll show some tougher examples, which should help provide more exposure. Forget three sub problems; one problem, the chain matrix multiplication problem, uses O(n) subproblems!
A little over a year ago I went looking for somewhat involved real world applications to motivate a discussion of dynamic programming, and I quickly stumbled into options valuation, specifically the Binomial Option Pricing Model (BOPM).
I originally came across dynamic programming when attempting to implement the "seam carving" algorithm used in content aware image resizing (and, to my understanding, used in a handful of smart image editing features in Photoshop these days)
I think the biggest problem with dynamic programming is its name. I'm not sure what I would call it, but "iterative memoization" comes close for the bottom-up approach.
The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.[11] The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.
https://www.udacity.com/course/introduction-to-graduate-algo...