[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