Hacker News Reader

Comment by da39a3ee | Hacker News Reader

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-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-stoc...)

View on HN

The 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.

OK, 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.

Fibonacci 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-teac...

I 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.

Yes, there is a natural way to solve these recursively. Here is an example: 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-stoc...

> 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.

The 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.

Reply on news.ycombinator.com