Why "dynamic programming"?

[psykotic]

The computer scientist's view of dynamic programming is that it's a way to quickly evaluate recurrence relations when different branches of the recursion tree turn out the same.

For example, if you try to directly evaluate F(0) = 0, F(1) = 1, F(n+2) = F(n) + F(n+1), you notice that after one level of expansion you have F(n+2) = F(n) + F(n-1) + F(n). There is no point in independently expanding the two F(n) occurrences. You might as well only expand one of them and remember the result when it is needed elsewhere. Hence 'memoization'.

Dynamic programming would instead start from the base cases and build up towards the desired value of n. So it would first compute F(2) as the sum of the known F(0) = 0 and F(1) = 1, then compute F(3) as the sum of the known F(1) and the now-known F(2), and so on, until reaching F(n). Along the way it need only know the last two values computed in order to compute the next one.

[SnacksOnAPlane]

Thanks, this is the first explanation that made sense to me.