[candeira]

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

[chillee]

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]

> 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

"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]

Yeah, you're right. The subproblems must overlap.

[candeira]

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.

[roenxi]

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]

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.

[anonytrary]

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