4 ms·
This is a widespread misconception: thinking of dynamic programming as just a form of memoized recursion is not the way to learn DP because it makes it extremel
by da39a3ee 3y ago
This is a widespread misconception: thinking of dynamic programming as just a form of memoized recursion is not the way to learn DP because it makes it extremely difficult to understand how to do the style of DP problems that involve filling out a 2D array.
For example, look at the "best time to buy and sell stock" series on leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ https://leetcode.com/problems/best-time-to-buy-and-sell-stoc....
These are much more naturally done by filling out an array, right? I've never done them with a recursion; I can't say I've thought hard about it -- is there a natural recursive solution?
(I linked to iii above but for anyone who hasn't tried them they are a great intro to DP problems; start with the first one: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...)
- deleted 3y ago[deleted]
- lifthrasiir 3y agoThe point is that you don't have to exactly fill the 2D array to solve the problem in that way. The 2D array is an optimization in this view, and can be safely replaced with a cache without breaking the correctness. Of course there is also some learned techniques specific to dynamic programming, and that makes it worthy to learn at some point because otherwise you will never think of them, but at its core dynamic programming is just a specific way of doing recursion.
- da39a3ee 3y agoOK, but, those are solved in just a few lines of code with 2D arrays. I'm not convinced it's helpful to approach them as recursions. Also, anyone who thinks they understand how to solve DP problems on leetcode because they understand how to memoize a fibonacci recursion is in for a rather large disappintment.
- lifthrasiir 3y agoFibonacci recursion is a bad example for DP because it is obvious how to do that. You need to teach a generative recursion, as pointed out by Shriram Krishnamurthi [1]. Once you've got a hang about a generative recursion DP is a space optimization on top of that. [1] https://parentheticallyspeaking.org/articles/how-not-to-teach-recursion/ https://parentheticallyspeaking.org/articles/how-not-to-teac...
- qsantos 3y agoI agree with that article that recursion is better introduced with relevant data structures than with Fibonacci. And I agree that Fibonacci is also too simple to explain dynamic programming, which is why I showed how it works with edit distance, and they with AoC 2023-12-18.
- tylerhou 3y agoYes, there is a natural way to solve these recursively. Here is an example: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/1146512107 https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... Not the best runtime (I could use a multidimensional array instead of an hash map for the cache, and recursion is "slow" in Python), but it's a clear solution. Given a recursive solution, it is also "trivial" to convert it into filling an array by visiting the recursive states in reverse topological order. So here is a submission that fills in the array: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/1146519236 https://leetcode.com/problems/best-time-to-buy-and-sell-stoc...
- deleted 3y ago[deleted]
- qsantos 3y agoThe issue I have with not connecting dynamic programming with caching is that it becomes an exercise in cleverness, and many people just give up. It was pretty fun in school, but if I need colleagues to ramp up on it, I need a more effective approach. Sure, they might not grok the full theory right away, but they won't use it at all, and definitely won't get to the theory, if they think it's too abstract for them.
- thdespou 3y ago> DP algorithms are "just" clever ways to cache a recursion It does't work all the time like that since caching increases the Space Complexity. There are DP problems that can be solved without storing all possible values in an array.