I always considered memoization a type of dynamic programming, rather than something different from dynamic programming. Wikipedia at least uses this same nomen

I always considered memoization a type of dynamic programming, rather than something different from dynamic programming. Wikipedia at least uses this same nomenclature - http://en.wikipedia.org/wiki/Dynamic_programming http://en.wikipedia.org/wiki/Dynamic_programming Anyways, there are cases when memoization takes orders of magnitude more memory. Consider a problem where calculating F(x, y) is dependent on F(x - 1, y) and F(x, y - 1). (Recursively calculating n choose k is one such example.) Let's say F(x, 0) and F(y, 0) are non-recursive, they just take O(1) time. If you use memoization, in order to find F(n, n) you will take O(n^2) memory. But if you fill an array, you can calculate all the F(1, x), then all the F(2, x), and once you have done all the F(2, x) you don't need the memory for the F(1, x) any more. Et cetera. So you only need O(n) memory.