Memoization or Tabulation approach for Dynamic programming

algorithm recursion time-complexity dynamic-programming
Mady picture Mady · Aug 20, 2012 · Viewed 10k times · Source

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?

Answer

behnam picture behnam · Aug 20, 2012

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.

Related questions

What is the space complexity of a recursive fibonacci algorithm?

This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition) int fibonacci(int i) { if(i == 0) return 0; if(i == 1) return 1; return fibonacci(i-1) + fibonaci(i-2); } After watching the video on the time complexity of …

Read More
What is tail recursion?

Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?

Read More
Finding height in Binary Search Tree

I was wondering if anybody could help me rework this method to find the height of a binary search tree. So far, my code looks like this. However, the answer I'm getting is larger than the actual height by 1. But …

Read More