Memoization or Tabulation approach for Dynamic programming

Viewed 12202

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?

4 Answers

First understand what is dynamic programming? If a problem at hand can be broken down to sub-problems whose solutions are also optimal and can be combined to reach solution of original/bigger problem. For such problems, we can apply dynamic programming. It's way of solving a problem by storing the results of sub-problems in program memory and reuse it instead of recalculating it at later stage.

Remember the ideal case of dynamic programming usage is, when you can reuse the solutions of sub-problems more than one time, otherwise, there is no point in storing the result.

Now, dynamic programming can be applied in bottom-up approach(Tabulation) and top-down approach(Memoization).

Tabulation: We start with calculating solutions to smallest sub-problem and progress one level up at a time. Basically follow bottom-up approach. Here note, that we are exhaustively finding solutions for each of the sub-problems, without knowing if they are really neeeded in future.

Memoization: We start with the original problem and keep breaking it one level down till the base case whose solution we know. In most cases, such breaking down(top-down approach) is recursive. Hence, time taken is slower if problem is using each steps sub-solutions due to recursive calls. But, in case when all sub-solutions are not needed then, Memoization performs better than Tabulation.

I found this short video quite helpful: https://youtu.be/p4VRynhZYIE

Related