3 ms·
Glad 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 knowi
by akdas 7y ago
Glad 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!