Dynamic programming vs Memoization vs Tabulation

Dynamic programming vs 

Memoization vs Tabulation

Dynamic programming is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decision or it  is a technique for solving problems recursively. 

It can be implemented by memoization or tabulation.

1. Memoization: Top Down
2. Tabulation: Bottom Up

Dynamic programming

Dynamic programming, DP for short, can be used when the computations of sub-problems overlap.

If you’re computing for instance fib(3) (the third Fibonacci number), a naive implementation would compute fib(1) twice:

With a more clever DP implementation, the tree could be collapsed into a graph (a DAG):

It doesn’t look very impressive in this example, but it’s in fact enough to bring down the complexity from O(2n) to O(n). Here’s a better illustration that compares the full call tree of fib(7) (left) to the corresponding collapsed DAG:

This improvement in complexity is achieved regardless of which DP technique (memoization or tabulation) is used.

Memoization

Memoization refers to the technique of caching and reusing previously computed results or we can say it is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same input s occur again.

 Here’s a comparison of a square function and the memoized version:

A memoized fib function would thus look like this:

As you can see fib_mem(k) will only be computed at most once for each k. (Second time around it will return the memoized value.)

This is enough to cause the tree to collapse into a graph as shown in the figures above. For fib_mem(4) the calls would be made in the following order:

This approach is top-down since the original problem, fib_mem(4), is at the top in the above computation.

Tabulation

Tabulation is similar in the sense that it builds up a cache, but the approach is different. A tabulation algorithm focuses on filling the entries of the cache, until the target value has been reached..

While DP problems, such as the Fibonacci computation, are recursive in nature, a tabulation implementation is always iterative.

The tabulation version of fib looks like this:

The computation of fib_tab(4) can be described as follows:

As opposed to the memoization technique, this computation is bottom-up since original problem, fib_tab(4), is at the bottom of the computation.

**NOTE: Pseudo-tabulation and a bottom-up approach has better memory complexity when we do not need to “remember” all previous solutions. (In Fibonacci for example, only the last 2 values must be remembered)

Tabulation vs Memoization:

	Tabulation	Memoization
Subproblem solving	If all subproblems must be solved at least once, a bottom-up dynamic programming algorithm usually outperforms a top-down memoized algorithm by constant factor.	If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are differently required
Speed	Fast, as we directly access previous states from the table	Slow due to lot of recursive calls and return statement
State	State transition relation is difficult to think	State transition relation is easy to think
Code	Code gets complicated when lot of condition are required	Code is easy and less complicated
Table Entries	In Tabulated version, starting from the first entry, all entries are filled one by one.	Unlike the Tabulated version, all entries of the lookup table are not necessarily filled Memoized version. The table is filled on demand
Control	In the Tabulation approach we have more control over what data to save for later.	In other hand inside a memoized function it is hard to make a decision on what previous results can be discarded.