4 ms·

It's good that the article points out that DP algorithms are "just" clever ways to cache a recursion. Looking for a recursive solution is certainly the best way

It's good that the article points out that DP algorithms are "just" clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution, in my experience -- if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a "bottom-up" DP, since it only ever computes solutions that we definitely need). With enough practice, it's usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn't matter if there are large numbers of subproblems in the call tree -- what's important is that there are a relatively small number of distinct subproblems. (Since there's no point caching a result that's only ever needed one time.) And that's where the difficulty tends to lie: Figuring out how to partition the original problem into few enough distinct subproblems.

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 ago
  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.
  - da39a3ee 3y ago
    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.
    - lifthrasiir 3y ago
      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-teach-recursion/ https://parentheticallyspeaking.org/articles/how-not-to-teac...
      - qsantos 3y ago
        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.
- tylerhou 3y ago
  Yes, 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 ago
  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.
- 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.
nsonha 3y ago
> DP algorithms are "just" clever ways to cache a recursion This is what made it click to me. When I was in university, perhaps because of the prevalence of procedural programming at the time (as opposed to FP), DP looked magic to me with the bottom-up tabularization examples in the textbook. Practically that is the way to do it because tail-call elimination isn't always applicable, but I wish they's taught us the more intuitive way to look at it first (top-down, cache a recursion)
- OskarS 3y ago
  The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization, you don't know which subproblems you need to store at any given, but going bottom-up, you do, and you can usually be much more clever about memory usage and overhead. The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1). This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N). Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.
  - hansvm 3y ago
    I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying. I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear. Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better. [0] https://github.com/hmusgrave/zdps https://github.com/hmusgrave/zdps
dataflow 3y ago
The best analogy I have here is that saying "DP is just caching/memoization" is like saying "investment is just buying stuff and selling them later." Regardless of how technically accurate it might be, it misses such massive complexities and difficulties in the topic that it just makes you look silly rather than insightful.
- natpalmer1776 3y ago
  Would you prefer someone start learning the principles of investing from an initial premise of “investment is just spending money to make money” or “investment is just buying something for less than it will be worth in the future” Both are technically correct and both statements are vast oversimplifications of a complex subject, however the second statement leads into more advanced topics naturally, creating a smoother progression of knowledge that builds on itself. Every complex topic generally starts with a few foundational bits of knowledge that support the whole house of cards. Pick the wrong foundational bits and you won’t get as far.
  - dataflow 3y ago
    I certainly don't disagree that there should be a solid foundation here; I just think this is the wrong foundation, for what I believe to be good reasons (some of which I'll get to below) - mainly, it confuses the concept with the implementation mechanics. Instead... I find it much more productive to start teaching this with the fundamentals of problem-solving techniques, as follows: - One method for solving complex problems is to divide them into separate subproblems that are simpler to solve. We call this "divide-and-conquer", as you've seen in [blah, e.g. mergesort]. Observe that this technique decomposes your subproblem structure into a tree. (Draw a picture.) - Another (more advanced) method for solving complex problems is to find subproblems that might potentially overlap, and then find a clever way to combine their solutions into the final answer. An example here is finding the shortest N-hop path by finding the shortest (N-1)-hop paths, and picking out the shortest of those to find the shortest N-hop path. Observe that this technique decomposes your subproblem structure into a DAG form. (Draw a picture.) Take a moment to read the above... notice the lack of any mention of caching/memoization/tables, etc.? That's not an accident. It's because those are optimizations to DP, not the core idea! Before you can even start talking about "how do I solve this quickly", the question you need to answer is "what systematic method can I use to solve this at all?" The central idea there is the decomposition of the problem into a tree vs. DAG structure. Once that sinks in, the question of how to make it faster (or whether to use recursion vs. iteration) is secondary, and also far more obvious to figure out on your own. Moreover, this also lets the student realize that you can (sometimes) speed up divide-and-conquer with memoization, too. Which also hammers home the point that such an optimization is very much distinct from the technique itself!
dsego 3y ago
I remember learning about the knapsack problem and trying out recursive ways to solve it as well. https://github.com/dsego/codility/blob/main/knapsack.js https://github.com/dsego/codility/blob/main/knapsack.js
Shorel 3y ago
Agree. When I first learned the subject, my first thought was: As fancy as that feature is, it should be called array memoization, or call stack memoization. The term "dynamic programming" should be reserved for something better. IMO.
- vanderZwan 3y ago
  I'm sure you know this (since in my experience the history of the name is usually taught together with the technique), but for those reading along: the name "dynamic programming" originates from the late forties, early fifties. While the "office politics"-related motivation Richard Bellman gives for the name cannot be completely true due to anachronisms[0], it still fits with terms that made sense at the time, before the modern usage of "programming" existed: > The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems (...). The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization. I fully agree that would be nice if we relegated "dynamic programming" to a confusing historical umbrella term, and switched to less confusing names, like the ones you suggested. In that sense it is similar to "trie" - it's a funny pun, but incredibly impractical for verbal communication especially. It would be so much better if we all decided to just use "prefix tree" or "prefix search tree" and avoid the ambiguity. [0] https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History
vishnugupta 3y ago
> what's important is that there are a relatively small number of distinct subproblems. This is the crucial part IMO. Whether the larger algorithm is recursive or iterative etc is secondary. But yes DP usually tends to show up in recursive algorithms most often.

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 ago
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.
- da39a3ee 3y ago
  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.
  - lifthrasiir 3y ago
    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-teach-recursion/ https://parentheticallyspeaking.org/articles/how-not-to-teac...
    - qsantos 3y ago
      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.
tylerhou 3y ago
Yes, 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 ago
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.
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.

nsonha 3y ago

> DP algorithms are "just" clever ways to cache a recursion This is what made it click to me. When I was in university, perhaps because of the prevalence of procedural programming at the time (as opposed to FP), DP looked magic to me with the bottom-up tabularization examples in the textbook. Practically that is the way to do it because tail-call elimination isn't always applicable, but I wish they's taught us the more intuitive way to look at it first (top-down, cache a recursion)

OskarS 3y ago
The bottom-up tabularization isn't always necessary, but it's a key technique that is not just "avoiding overhead" or whatever. Doing the top-down memoization, you don't know which subproblems you need to store at any given, but going bottom-up, you do, and you can usually be much more clever about memory usage and overhead. The obvious example is Fibonacci numbers: the "top down" memoized version needs to store every Fibonacci number in memory, because you don't know what number the recursion is asking for. But if you do it "bottom up", you know that to calculate f(N), you only need f(N-2) and f(N-1). Therefore, you only need to store the last two numbers, reducing your memory usage from O(n) to O(1). This principle almost always applies in DP problems: for the "edit distance" problem, the number possible values for the function is N^2 (where N is the size of the two words you need to compare, assuming they're similar sizes), so the memoized version takes O(N^2) memory. But if you do it the "bottom up" version, you realize that to calculate all values in a row, you just need the previous row of values. So it takes memory from O(N^2) to O(N). Point being: turning the recursion "upside down" is not just a thing you do to be clever (or to avoid "function calling overhead", something like that), it has very real algorithmic benefits, usually because it takes MUCH less memory to do it like that.
- hansvm 3y ago
  I think their point is that naive caching attempts still result in duplicate work, and if you start by viewing the problem recursively then DP is a clever insight allowing you to avoid that duplicate work. You're right; it's not _just_ function calling overhead or anything minor; it often represents major Big-O improvements. I think that's in alignment with what they're saying. I like your insight about Fibonacci needing less state than a naive DP would suggest. Diving into that a bit, DP implementations represent a DAG. More importantly, for all the problems that easily fit into DP that DAG has small numbers of "local" connections -- you can partition it into at least O(some_meaningful_dimension) many topologically sorted levels where each level only depends on a small, known, finite number of previous levels (often 1-2), not deeper DAG nodes. A clever choice of order of operations then looks for a min-cut on that graph, proceeding through those levels. Fib has at most O(n) levels and at least O(n) state for naive DP, so a clever implementation has O(n/n)=O(1) state. Edit distance has at most O(n) levels and at least O(n^2) state, so a clever implementation has O(n^2/n)=O(n) state. I did something similar for some DP probability calculation [0], and it reduces state from quadratic to linear. Fibonacci is, slightly pedantically, one of the worst algorithms to analyze this way. Only the smallest inputs actually fit in machine integers, and the exponential increase in the size of any bigints involved really puts a damper on a naive Big-O analysis. Fib mod 2^64 (or some biggish prime) fits into the spirit of things better. [0] https://github.com/hmusgrave/zdps https://github.com/hmusgrave/zdps

dataflow 3y ago

The best analogy I have here is that saying "DP is just caching/memoization" is like saying "investment is just buying stuff and selling them later." Regardless of how technically accurate it might be, it misses such massive complexities and difficulties in the topic that it just makes you look silly rather than insightful.

natpalmer1776 3y ago
Would you prefer someone start learning the principles of investing from an initial premise of “investment is just spending money to make money” or “investment is just buying something for less than it will be worth in the future” Both are technically correct and both statements are vast oversimplifications of a complex subject, however the second statement leads into more advanced topics naturally, creating a smoother progression of knowledge that builds on itself. Every complex topic generally starts with a few foundational bits of knowledge that support the whole house of cards. Pick the wrong foundational bits and you won’t get as far.
- dataflow 3y ago
  I certainly don't disagree that there should be a solid foundation here; I just think this is the wrong foundation, for what I believe to be good reasons (some of which I'll get to below) - mainly, it confuses the concept with the implementation mechanics. Instead... I find it much more productive to start teaching this with the fundamentals of problem-solving techniques, as follows: - One method for solving complex problems is to divide them into separate subproblems that are simpler to solve. We call this "divide-and-conquer", as you've seen in [blah, e.g. mergesort]. Observe that this technique decomposes your subproblem structure into a tree. (Draw a picture.) - Another (more advanced) method for solving complex problems is to find subproblems that might potentially overlap, and then find a clever way to combine their solutions into the final answer. An example here is finding the shortest N-hop path by finding the shortest (N-1)-hop paths, and picking out the shortest of those to find the shortest N-hop path. Observe that this technique decomposes your subproblem structure into a DAG form. (Draw a picture.) Take a moment to read the above... notice the lack of any mention of caching/memoization/tables, etc.? That's not an accident. It's because those are optimizations to DP, not the core idea! Before you can even start talking about "how do I solve this quickly", the question you need to answer is "what systematic method can I use to solve this at all?" The central idea there is the decomposition of the problem into a tree vs. DAG structure. Once that sinks in, the question of how to make it faster (or whether to use recursion vs. iteration) is secondary, and also far more obvious to figure out on your own. Moreover, this also lets the student realize that you can (sometimes) speed up divide-and-conquer with memoization, too. Which also hammers home the point that such an optimization is very much distinct from the technique itself!

dsego 3y ago

I remember learning about the knapsack problem and trying out recursive ways to solve it as well. https://github.com/dsego/codility/blob/main/knapsack.js https://github.com/dsego/codility/blob/main/knapsack.js

Shorel 3y ago

Agree. When I first learned the subject, my first thought was: As fancy as that feature is, it should be called array memoization, or call stack memoization. The term "dynamic programming" should be reserved for something better. IMO.

vanderZwan 3y ago
I'm sure you know this (since in my experience the history of the name is usually taught together with the technique), but for those reading along: the name "dynamic programming" originates from the late forties, early fifties. While the "office politics"-related motivation Richard Bellman gives for the name cannot be completely true due to anachronisms[0], it still fits with terms that made sense at the time, before the modern usage of "programming" existed: > The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems (...). The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization. I fully agree that would be nice if we relegated "dynamic programming" to a confusing historical umbrella term, and switched to less confusing names, like the ones you suggested. In that sense it is similar to "trie" - it's a funny pun, but incredibly impractical for verbal communication especially. It would be so much better if we all decided to just use "prefix tree" or "prefix search tree" and avoid the ambiguity. [0] https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History

vishnugupta 3y ago

> what's important is that there are a relatively small number of distinct subproblems. This is the crucial part IMO. Whether the larger algorithm is recursive or iterative etc is secondary. But yes DP usually tends to show up in recursive algorithms most often.