3 ms·

Dynamic Programming and memoization are definitely related techniques, but they are emphatically _not_ the same. Memoization is a black-box approach that can be

Dynamic Programming and memoization are definitely related techniques, but they are emphatically _not_ the same. Memoization is a black-box approach that can be applied to a generic recursive top-down, depth-first algorithm. Dynamic Programming is about rewriting the recursive top-down algorithm in a bottom-up, breadth-first manner. Shriram Krishnamurthi explains it best: https://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html https://blog.racket-lang.org/2012/08/dynamic-programming-ver...

chillee 8y ago
This is one definition, but I don't think it's the common one. The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler overlapping subproblems that can be solved independently. Solving it with recursion/memoization vs. bottom-up is merely an implementation detail, while DP refers to a class of algorithms. EDIT: Corrected definition of DP.
- rifung 8y ago
  > The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler subproblems that can be solved independently I dont think that's sufficient? I thought DP also implies you actually reuse the answers from subproblems. From https://en.m.wikipedia.org/wiki/Dynamic_programming https://en.m.wikipedia.org/wiki/Dynamic_programming "There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead"
  - chillee 8y ago
    Yeah, you're right. The subproblems must overlap.
- candeira 8y ago
  I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions. And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.
anonytrary 8y ago
This is a great explanation. Never thought of it like that.
roenxi 8y ago
It is a good write up, but it underscores the mystery of how DP ever got named as a technique. Memoization is a great general-purpose technique that covers pretty much all the obvious cases for DP to a reasonable standard. Its black-box nature allows for effective and well compartmentalised application. DP is an extremely complicated and invasive technique that requires rewriting algorithms to optimise for space & time use. It doesn't seem like the advantages of DP are enough to outweigh the neat design of memoisation. I'd rather see an interview question on implementing memoize in Python than writing a DP algorithm.
hvidgaard 8y ago
Dynamic programming is a mathematical term for a certain kind of problems that have certain properties and can be solved in a certain way. Memoization is specific form of caching for functions. That is all there is to it. Your link seems to conflate memoization with a global store that you must apply in an all or nothing fashion for functions. You do not, and calculating the n'th fibonacci number is a great example of how to use memoization without using O(n) space.

chillee 8y ago

This is one definition, but I don't think it's the common one. The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler overlapping subproblems that can be solved independently. Solving it with recursion/memoization vs. bottom-up is merely an implementation detail, while DP refers to a class of algorithms. EDIT: Corrected definition of DP.

rifung 8y ago
> The more common definition is that dynamic programming refers to solving a complicated problem by breaking it up into simpler subproblems that can be solved independently I dont think that's sufficient? I thought DP also implies you actually reuse the answers from subproblems. From https://en.m.wikipedia.org/wiki/Dynamic_programming https://en.m.wikipedia.org/wiki/Dynamic_programming "There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead"
- chillee 8y ago
  Yeah, you're right. The subproblems must overlap.
candeira 8y ago
I understand that DP requires turning a recursive, top-down algorithm into an iterative one by yes, reusing the overlap in the subsolutions. And Krishamurthi's definition is the clearer I've seen that doesn't include "memoized recursion" as a subset of Dynamic Programming.

anonytrary 8y ago

This is a great explanation. Never thought of it like that.

roenxi 8y ago

It is a good write up, but it underscores the mystery of how DP ever got named as a technique. Memoization is a great general-purpose technique that covers pretty much all the obvious cases for DP to a reasonable standard. Its black-box nature allows for effective and well compartmentalised application. DP is an extremely complicated and invasive technique that requires rewriting algorithms to optimise for space & time use. It doesn't seem like the advantages of DP are enough to outweigh the neat design of memoisation. I'd rather see an interview question on implementing memoize in Python than writing a DP algorithm.

hvidgaard 8y ago

Dynamic programming is a mathematical term for a certain kind of problems that have certain properties and can be solved in a certain way. Memoization is specific form of caching for functions. That is all there is to it. Your link seems to conflate memoization with a global store that you must apply in an all or nothing fashion for functions. You do not, and calculating the n'th fibonacci number is a great example of how to use memoization without using O(n) space.