5 ms·

Would it be wrong to just think "memoization" when you hear "dynamic programming"? The missing part may be intelligently breaking up the problem to use memoizat

Would it be wrong to just think "memoization" when you hear "dynamic programming"? The missing part may be intelligently breaking up the problem to use memoization?

ecshafer 3y ago
Yes it would be wrong in my book. First i think a obvious counter example of memoization can be used outside of dynamic programing. Otherwise you can do most dynamic programming algorithms with storing the results in a table, and searching the table afterwards for the best answer. Memoization is basically a strategy to speed up algorithms.
- sk11001 3y ago
  > First i think a obvious counter example of memoization can be used outside of dynamic programing This isn't relevant, the quesion is whether there are dynamic programming solutions which do not involve memoization.
  - eru 3y ago
    Well, dynamic programming also tells you when you can drop your 'memoization' caches.
JohnKemeny 3y ago
That's exactly how I teach dynamic programming. First solve it recursively, then add memoization (I call that top-down). Then notice that recursion and memoization has some overhead, and construct the table from bottom-up, remove the recursive call, and voila, dynamic programming.
- throwaway2037 3y ago
  This sounds like a promising teaching technique. Do you have a slide deck to share? I am sure HN crowd would be interested to read.
  - globular-toast 3y ago
    It's in TFA...
jltsiren 3y ago
Memoization is a more general technique. It's often little more than caching the results you happened to compute, in case you need them again in the future. Dynamic programming is systematic memoization. You solve subproblems of increasing size, until you reach a solution to the full problem. "Inductive algorithm" would be kind of appropriate term, as the typical dynamic programming algorithm is effectively a proof by induction. Unfortunately that term already has other meanings.
- deaddodo 3y ago
  And "dynamic programming" is an insanely general term that leetcode enthusiasts have pigeonholed into meaning memoized reduction. It can describe dynamic dispatch, code morphing/rewriting, dynamic loading, etc. I would argue "memoization", while still a bad term, is far more specific and descriptive of what's happening than "dynamic programming".
  - greyw 3y ago
    The term "Dynamic programming" comes from mathematics of the 1940s before modern programming languages even existed. It's about a certain way to do optimization. This is also how it is used by "leetcode enthusiasts" so imo they are using it correctly. Nowadays, you could naturally confuse dynamic programming with the things you have listed.
    - nihzm 3y ago
      Exactly! I have already linked it in another thread but see this link below for the mathematical definition of dynamic programming: https://web.mit.edu/dimitrib/www/DP_Slides.pdf https://web.mit.edu/dimitrib/www/DP_Slides.pdf
    - deaddodo 3y ago
      > This is also how it is used by "leetcode enthusiasts" so imo they are using it correctly. I never said they used it incorrectly. In fact, inversely, I tacitly acknowledged the fact that it was used correctly. I said they pigeonholed a generalized phrase into a specific use case. E.g. a word/phrase that can be used to describe many similar but distinct concepts in the same field, as you yourself acknowledge. If you're going to take umbrage with someone's words, it's better not to misunderstand them or misphrase them.
kevindamm 3y ago
There are dynamic programming solutions not based on memoization. See for example finding the longest common substring between two strings. Memoization will not help as much because you only need the table's left and up cells once. In general, if the problem's sub-problems have a lot of overlap and the optimal subproblem must be part of the optimal overall solution, you've got an opportunity for dynamic programming. Saying memoization is the only kind of dynamic programming is like saying hash tables are the only abstract data type.
- deleted 3y ago
  [deleted]
- recursive 3y ago
  The left of the up is the up of the left.
  - kevindamm 3y ago
    Yeah, I had a momentary misgiving when I hit send and thought (_well, the cell is used twice_) but in practice it is still very different than what would be considered memoization. You can make it work with just two rows at a time, forgetting all the calculated values of the earlier rows. You can also do it in one row if you work backwards in each row. If anything, it's a cache with a very specific eviction policy. I had a whole other paragraph where I nearly convinced myself it's the same here for LCS so I'm just going to stop myself here. If you look up any texts that describe LCS they don't refer to it as using memoization. Let's not confuse things.
    - n2d4 3y ago
      > If you look up any texts that describe LCS they don't refer to it as using memoization. I challenge that actually, several resources online consider it memoization (I would too): https://www.geeksforgeeks.org/longest-common-subsequence-dp-using-memoization/ https://www.geeksforgeeks.org/longest-common-subsequence-dp-...
GuB-42 3y ago
To my approach to dynamic programming, memoization is step 2 of 3. 1- find a recursive algorithm 2- memoization 3- make it iterative / bottom-up 3b- if possible, optimize for space Step 3 is the most characteristic part of dynamic programming, but if you stopped at step 2, it would still qualify, I think, but it would not be as efficient as it could be. Another way to think of step 3 would be: memoization is about caching, is there a way to pre-fill the cache?
- naet 3y ago
  Where I have the most trouble is usually going from recursive to iterative. It's pretty easy for me to understand the recursive + memoization, but when that ends up being taken off the table due to various inefficiencies of recursion I often get a little stuck.
- cubefox 3y ago
  This makes it clear why dynamic programming is not easy. The problem occurs already in step 1 -- we naturally tend to think in loops, not recursions. So before you find a recursive algorithm, you probably come up with a loop algorithm first. Then you have to try to convert the loop into recursion, then go back to loops that use caching. And hope that the result is more efficient than the loop algorithm you started with.
  - WJW 3y ago
    Speak for yourself, there are dozens (dozens!) of us for which recursion is the more natural way to think about most algorithms. Joking aside, DP is very straightforward in more functional languages like Haskell where recursion is the default way to do iteration anyway.
    - cubefox 3y ago
      And I think people don't like functional programming languages because they don't like recursion. Even cookbooks use loops!
  - GuB-42 3y ago

Would it be wrong to just think "memoization" when you hear "dynamic programming"? The missing part may be intelligently breaking up the problem to use memoization?

ecshafer 3y ago

Yes it would be wrong in my book. First i think a obvious counter example of memoization can be used outside of dynamic programing. Otherwise you can do most dynamic programming algorithms with storing the results in a table, and searching the table afterwards for the best answer. Memoization is basically a strategy to speed up algorithms.

sk11001 3y ago
> First i think a obvious counter example of memoization can be used outside of dynamic programing This isn't relevant, the quesion is whether there are dynamic programming solutions which do not involve memoization.
- eru 3y ago
  Well, dynamic programming also tells you when you can drop your 'memoization' caches.

JohnKemeny 3y ago

That's exactly how I teach dynamic programming. First solve it recursively, then add memoization (I call that top-down). Then notice that recursion and memoization has some overhead, and construct the table from bottom-up, remove the recursive call, and voila, dynamic programming.

throwaway2037 3y ago
This sounds like a promising teaching technique. Do you have a slide deck to share? I am sure HN crowd would be interested to read.
- globular-toast 3y ago
  It's in TFA...

jltsiren 3y ago

Memoization is a more general technique. It's often little more than caching the results you happened to compute, in case you need them again in the future. Dynamic programming is systematic memoization. You solve subproblems of increasing size, until you reach a solution to the full problem. "Inductive algorithm" would be kind of appropriate term, as the typical dynamic programming algorithm is effectively a proof by induction. Unfortunately that term already has other meanings.

deaddodo 3y ago
And "dynamic programming" is an insanely general term that leetcode enthusiasts have pigeonholed into meaning memoized reduction. It can describe dynamic dispatch, code morphing/rewriting, dynamic loading, etc. I would argue "memoization", while still a bad term, is far more specific and descriptive of what's happening than "dynamic programming".
- greyw 3y ago
  The term "Dynamic programming" comes from mathematics of the 1940s before modern programming languages even existed. It's about a certain way to do optimization. This is also how it is used by "leetcode enthusiasts" so imo they are using it correctly. Nowadays, you could naturally confuse dynamic programming with the things you have listed.
  - nihzm 3y ago
    Exactly! I have already linked it in another thread but see this link below for the mathematical definition of dynamic programming: https://web.mit.edu/dimitrib/www/DP_Slides.pdf https://web.mit.edu/dimitrib/www/DP_Slides.pdf
  - deaddodo 3y ago
    > This is also how it is used by "leetcode enthusiasts" so imo they are using it correctly. I never said they used it incorrectly. In fact, inversely, I tacitly acknowledged the fact that it was used correctly. I said they pigeonholed a generalized phrase into a specific use case. E.g. a word/phrase that can be used to describe many similar but distinct concepts in the same field, as you yourself acknowledge. If you're going to take umbrage with someone's words, it's better not to misunderstand them or misphrase them.

kevindamm 3y ago

There are dynamic programming solutions not based on memoization. See for example finding the longest common substring between two strings. Memoization will not help as much because you only need the table's left and up cells once. In general, if the problem's sub-problems have a lot of overlap and the optimal subproblem must be part of the optimal overall solution, you've got an opportunity for dynamic programming. Saying memoization is the only kind of dynamic programming is like saying hash tables are the only abstract data type.

deleted 3y ago
[deleted]
recursive 3y ago
The left of the up is the up of the left.
- kevindamm 3y ago
  Yeah, I had a momentary misgiving when I hit send and thought (_well, the cell is used twice_) but in practice it is still very different than what would be considered memoization. You can make it work with just two rows at a time, forgetting all the calculated values of the earlier rows. You can also do it in one row if you work backwards in each row. If anything, it's a cache with a very specific eviction policy. I had a whole other paragraph where I nearly convinced myself it's the same here for LCS so I'm just going to stop myself here. If you look up any texts that describe LCS they don't refer to it as using memoization. Let's not confuse things.
  - n2d4 3y ago
    > If you look up any texts that describe LCS they don't refer to it as using memoization. I challenge that actually, several resources online consider it memoization (I would too): https://www.geeksforgeeks.org/longest-common-subsequence-dp-using-memoization/ https://www.geeksforgeeks.org/longest-common-subsequence-dp-...

GuB-42 3y ago

To my approach to dynamic programming, memoization is step 2 of 3. 1- find a recursive algorithm 2- memoization 3- make it iterative / bottom-up 3b- if possible, optimize for space Step 3 is the most characteristic part of dynamic programming, but if you stopped at step 2, it would still qualify, I think, but it would not be as efficient as it could be. Another way to think of step 3 would be: memoization is about caching, is there a way to pre-fill the cache?

naet 3y ago
Where I have the most trouble is usually going from recursive to iterative. It's pretty easy for me to understand the recursive + memoization, but when that ends up being taken off the table due to various inefficiencies of recursion I often get a little stuck.
cubefox 3y ago
This makes it clear why dynamic programming is not easy. The problem occurs already in step 1 -- we naturally tend to think in loops, not recursions. So before you find a recursive algorithm, you probably come up with a loop algorithm first. Then you have to try to convert the loop into recursion, then go back to loops that use caching. And hope that the result is more efficient than the loop algorithm you started with.
- WJW 3y ago
  Speak for yourself, there are dozens (dozens!) of us for which recursion is the more natural way to think about most algorithms. Joking aside, DP is very straightforward in more functional languages like Haskell where recursion is the default way to do iteration anyway.
  - cubefox 3y ago
    And I think people don't like functional programming languages because they don't like recursion. Even cookbooks use loops!
- GuB-42 3y ago