Memoization or Tabulation approach for Dynamic programming

27
votes

There are many problems that can be solved using Dynamic programming e.g. Longest increasing subsequence. This problem can be solved by using 2 approaches

  1. Memoization (Top Down) - Using recursion to solve the sub-problem and storing the result in some hash table.
  2. Tabulation (Bottom Up) - Using Iterative approach to solve the problem by solving the smaller sub-problems first and then using it during the execution of bigger problem.

My question is which is better approach in terms of time and space complexity?

3
algorithmrecursiontime-complexitydynamic-programming
Your second option isn't really dynamic-programming, it's more decrease and conquer. It is dependent on the problem size and what the problem is trying to solve in terms of analysis. – squiguy
Depends of problem of course. – barak1412
If there were a cut-and-dried, universal answer, life would be simpler and all the textbooks would just teach you the "correct" way. But there isn't a universal answer. Also, the word is 'memoization.' No 'R'. – Novak
why it is called memoization? memorization seems to be the apt word as we memorize the result of the smaller sub-problems. – Mady
@Mady en.wikipedia.org/wiki/Memoization#Etymology – Ionuț G. Stan

3 Answers

40
votes

Short answer: it depends on the problem!

Memoization usually requires more code and is less straightforward, but has computational advantages in some problems, mainly those which you do not need to compute all the values for the whole matrix to reach the answer.

Tabulation is more straightforward, but may compute unnecessary values. If you do need to compute all the values, this method is usually faster, though, because of the smaller overhead.

1
votes

Asymptotically a dynamic programming implementation that is top down is the same as going bottom up, assuming you're using the same recurrence relation. However, bottom up is generally more efficient because of the overhead of recursion which is used in memoization.

-5
votes

If the problem has overlapping sub-problems property then use Memoization, else it depends on the problem