Top-down recursion can be memory-intensive because of building up the call stack. Can avoid by going bottom-up and using DP. Current point.
DP often involves making a binary decision at each (bottom-up) step, e.g., do I include this coin / item / character in my knapsack / sum / subsequence. If I do include it, is that more optimal (value or stock market profit or so on) than if I don't, where each calculation usually makes use of previously calculated optima or solutions to subproblems.
To get those previous locally optimal calculations, we generally use a matrix or list to store the previous solutions. But sometimes that can store more state than we really need, see e.g. the bottom-up Fibonacci implementation where we can store the answers to the previous subproblems we need in just 2 variables.
Always think: at step n, what happens if I *do* include this thing? What happens if I don't? What do I need to compare and take the max of? And how do I use my answer to step n-1?
Interview Cake:
"Dynamic programming is kind of like the next step up from greedy . You're taking that idea of "keeping track of what we need in order to update the best answer so far," and applying it to situations where the new best answer so far might not just have to do with the previous answer, but some other earlier answer as well.
So as you can see in this problem, we kept track of all of our previous answers to smaller versions of the problem (called "subproblems") in a big list called ways_of_doing_n_cents.
Again, same idea of keeping track of what we need in order to update the answer as we go, like we did when storing the max product of 2, min product of 2, etc in the highest product of 3 question. Except now the thing we need to keep track of is all our previous answers, which we're keeping in a list.
We built that list bottom-up, but we also talked about how we could do it top-down and memoize. Going bottom-up is cleaner and usually more efficient, but often it's easier to think of the top-down version first and try to adapt from there."
When we memoize (cache a subproblem's answer / recursive function's output so we don't need to recompute it again), the memoization dictionary probably needs to be outside the function to save/share state. I.e., make a class. Interview Cake #5: https://www.interviewcake.com/question/python/coin. Don't always have to, can sometimes just pass a default list or dict (be careful of the default mutable gotcha here).
Memoization is top-down depth-first and DP is bottom-up breadth-first:
No comments