Why does top down memoization use more memory than bottom up tabulation?
In the case of tabulation, if we order our subproblems in a way that some subproblems are used in the early phase and then never used again. For example in the Fibonacci series, the order of values being calculate and used again is as follows:
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
When we have used the results of 0 + 1 to compute 1, 1 + 1 to compute 2, and then 1+2 to compute 3. In the next calls, we don’t need to save the results of the first two statements anymore and those values can be discarded. So at any given time, we have to save only two values thus reducing the required space.
But in the case of memoization, we cannot order our subproblems due to recursion and have to save the results of all subproblems. Hence, we cannot optimize our problem in terms of memory being used.