Show HN: Python Recursion: A Trampoline from the Mutual Head to the...
Comments
My prof cleared everything up though. He said that DP is what naturally happens whenever you take a recursive algorithm and refactor it to put all the recursive calls into their own data structure. When you are doing recursive fibonacci, you are really just using the call stack as a linked list. So instead of making the recursive call, figure out how value N in the list relies on the previous values and then compute that directly.
For more complicated algorithms where the recursive call has N arguments, that means you need a N-dimensional array (worst case) to store your calls in.
After that lecture I was never scared of dynamic programming because I had a meta-algorithm to produce the DP solution.
1. Write a recursive algo (probably exponentially inefficent)
2. Figure out how to store recursive call data in a data structure
3. Figure out how to populate field (a,b) of the data structure, normally by combining/minimizing/maximizing (a,b-1), (a-1,b)
4. Figure out how to get the answer out of the data structure once you have filled it in