5 ms·
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.
by OmarIsmail 7y ago
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).
- akdas 7y agoGlad I was able to reach you at the right time :) 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!