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