Tabulation vs Memoization

Last Updated : 11 Dec, 2024

Tabulation and memoization are two techniques used to implement dynamic programming. Both techniques are used when there are overlapping subproblems (same subproblem is executed multiple times). Below is an overview of two approaches.

Memoization:

Top-down approach
Stores the results of function calls in a table.
Recursive implementation
Entries are filled when needed.

Tabulation:

Bottom-up approach
Stores the results of subproblems in a table
Iterative implementation
Entries are filled in bottom up manner from smallest size to final size.

	Tabulation	Memoization
State	State transition relation is difficult to think	State Transition relation is easy to think
Code	Code gets complicated when a lot of conditions are required	Code is easy to write by modifying the underlying recursive solution.
Speed	Fast, as we do not have recursion call overhead.	Slow due to a lot of recursive calls.
Subproblem solving	If all subproblems must be solved at least once, a bottom-up dynamic programming algorithm definitely outperforms a top-down memoized algorithm by a 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 definitely required
Table entries	In the 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 in Memoized version. The table is filled on demand.