[alangpierce]

> So "DP" is just recursion with memoization?

Sort of. "I know DP" doesn't just mean "I know what memoized recursion is". It means "I know how to take a problem, recognize that DP might help, frame it recursively with highly-overlapping subproblems, and use memoized recursion to implement an efficient algorithm for it". Especially in advanced cases, it take a lot of skill to look at a problem in just the right way that memoized recursion makes it computationally easy.

For example, sometimes you might have a problem where the simple DP approach takes n^3 space, but with some trickery you can get it down to n^2.

[tyingq]

So, what about something relatively straightforward? Like Fibonacci. Is it "DP" if I recurse+cache?

[alangpierce]

Yep, it's still certainly DP, in the same sense that 1 + 1 is addition, but understanding 1 + 1 doesn't necessarily mean that you've mastered addition.

[tyingq]

Just trying to understand the concept/name. I'm clearly not the only one confused.

Say I, at runtime, build a table of function pointers. Based on some attribute/test of the input that suggests a specific type of function is faster for that type of input.

If it's faster, but not exponentially faster than a naive solution...is that "dynamic"?

[alangpierce]

> is that "dynamic"?

Nope, DP is a bit more than "build a table" or "cache results". It's specifically about framing a problem recursively, and it needs to be the sort of recursion that has overlapping subproblems. For example, fib(8) and fib(7) will both call fib(6), which means that it's useful to cache fib(6). Some problems (like counting the number of nodes in a tree) are recursive but don't have overlapping recursion, so DP doesn't help with those.

(Sorry, I didn't mean my "addition" comment to sound condescending! I just meant that memoized recursive fibonacci is a simple example of DP, and the fact that it's (relatively) simple doesn't mean it's not DP.)

[tyingq]

Ahh, that "overlap" qualifier is helpful. I roughly get it now. Thanks!

The funny thing is that I'd much rather use something like this back and forth discussion in an interview. It tells me more than a coding test.

[slavik81]

The name "Dynamic Programming" was coined to be deliberately confusing by an early researcher in the field for the sake of maintaining research funding in a hostile environment [1]. Don't worry too much about the components of the name.

[1]: https://en.wikipedia.org/wiki/Dynamic_programming#History