Memoization or Tabulation approach for Dynamic programming

Question

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?

Tantalic

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. – Unprincipled

Depends of problem of course. – Umbilicate

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'. – Chuckchuckfull

why it is called memoization? memorization seems to be the apt word as we memorize the result of the smaller sub-problems. – Tantalic

@Tantalic en.wikipedia.org/wiki/Memoization#Etymology – Jolyn

Answer 1

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.

Seibel

Answer 2

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

Pow

Answer 3

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.

Envoy

I have a question regarding this.. Incase we use a hashset along with Memoization to store already calculated values, won't that make memoization as effecient as tabulation in most cases.. ? – Diluvium

Answer 4

The pedantic answer is: they're asymptotically identical.

The more nuanced answer is that top-down solutions are usually more intuitive and representative of the underlying recurrence relation inherent to a dynamic programming problem, lazily evaluating and enumerating larger subproblems before drilling down to the constituent base cases. Only in cases where you know for a fact that every sub-problem will be used and consolidated (e.g., Coin Change), do you stand to benefit from bottom-up over top-down.

It's all too common in DS&A courses and LeetCode editorials to immediately shun solutions that are top-down because of the dreaded "r-word^[1]", unfortunately. If implemented correctly, top-down DP can work with the compiler and result in well-executed optimizations that match or even beat bottom-up, calculated tabulations. Unstructured, ad-hoc problems that make good use of this "lazy evaluation" like the Combination Sum (I, II, III, IV) series can stand to benefit from this thought pattern, as well as branch-and-bound problems like the Advent of Code 2022 days 16 and 19 where a bottom-up solution will do nothing but increase the number of space heaters in your home.

A more interactive example I tend to give to people is the triangle of partition numbers used to represent the restricted partition problem. By studying the recurrence relation noted on the page (p(n, k) = p(n - 1, k = 1) + p(n - k, k)) you can both calculate the entire triangle bottom-up, or you can just calculate values on the fly (top-down), and manually tracing through a few sets of inputs will immediately paint one of the two methods in a relatively poor light.

---

^{[1] Recursion, mind you.}

Wirehaired

Answer 5

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

Witt

For overlapping sub-problems we can use Tabulation too. – Tantalic

Yes you can use, but memoization removes redundant computations – Witt

@Witt So does tabulation. – Greenfield