What is Tabulation?

Tabulation

As we discussed in the bottom-up approach, we start from the bottom, the smallest subproblem, or the base case. After evaluating the base case, we evaluate a slightly bigger problem and store its result. We continue doing this, i.e., build on the solution of smaller subproblems to evaluate bigger and bigger subproblems until we find the solution to our main problem.

In bottom-up dynamic programming, the process of storing results of evaluated subproblems in an array is called tabulation.

How is it different from memoization?

In memoization and top-down dynamic programming, we evaluated and stored results on an ad-hoc basis. We only evaluated something when it was needed. This means if a problem depends on only two subproblems, only those subproblems would have been evaluated. This comes naturally from the design of recursion. Moreover, the order in which we evaluated subproblems did not matter either. Evaluating Fibonacci(n) before Fibonacci(n-1) or vice versa did not have any effect on the result or running time of the algorithm.

This is not the case with tabulation. Here, we will have to evaluate almost every subproblem that lies between the base case and the main problem and we will have to do so in order. Thus, in tabulation, we typically use lists and arrays instead of hashtables. Lists force us to start from scratch and solve everything sequentially, which is the crux of bottom-up dynamic programming as well. For example, if we were writing an algorithm for the factorial of a number n using a bottom-up approach, we first establish a factorial of 0, then we will use it for factorial of 1, 2 and so on until we reach n. We can tabulate the results by keeping a list of size n, where each index will store the factorial against that index. For example at index 4, we will store 4!. Look at the code of the factorial algorithm below.

We have also given the code for a recursive algorithm to evaluate the factorial for comparison.