>>11
Memoization isn't really dynamic programming, but it's similar in principle. Memoization saves the results of *all* function calls whereas dynamic programming saves only those that will be needed again, and generally throws out a result that is no longer needed. Compare these two versions of fibs:
MEMOIZED:
fibt = {1, 1}
for i = 3, n do
fibt[i] = fibt[i - 1] + fibt[i - 2]
end
return fibt[n]
DYNAMICALLY PROGRAMMED:
i, j = 1, 1
for i = 3, n do
local t = i
i = i + j
j = t
end
return i
(the loop can be optimized to "
i = i + j; j = i - j", but dealing with t explicitly helps to explain the logic behind what is going on)
The difference between the two is that in the memoized version all previous values are stored, whereas in the dynamically programmed version only the last two values are stored, since they are the only ones that will be necessary to calculate the next value. Of course, there are problems where dynamic programming is extremely difficult or impossible to implement, since it is very hard to know which values are no longer needed.