What is the difference between memoization and tabulation in dynamic programming?
The difference is about when the answers are worked out. With memoization the answers are worked out as the search reaches them, and they are saved so that the same question is never answered twice. With tabulation you fill a table in order from the smallest case to the biggest, and then you read the answer out of the table.
the approach when the work happens the shape
----------------- ------------------------- ----------------------
memoization during the search a dictionary
tabulation before the search a list or a table
So both of them give the same answer, and they both turn an exponential search into a linear one. The difference is in how they are written and how they behave.
The first difference is the direction of the work. Memoization works from the big case down to the small case, because it starts with the whole problem and breaks it into smaller pieces. Tabulation works from the small case up to the big one, because it fills in the table in order and every entry only needs the entries before it.
The second difference is the space. Memoization usually uses a dictionary, and it only stores the states that the search actually reached. Tabulation fills every entry in the table, even the ones that the answer never needed. So tabulation can use more memory than memoization when many of the states are useless.
The third difference is the stack. Memoization is recursive, so it uses the call stack and it can hit the recursion limit on a big problem. Tabulation is a loop, so there is no stack at all and it can handle much bigger problems.
And there is one more difference that is worth knowing about. A bottom-up table is sometimes easier to write than the top-down version, because you can fill it in the order that you want and the answer is always at a known place. And the top-down version is sometimes easier to write, because you only have to describe the recurrence and the code finds the states for you.
So the rule to remember is this. Both of them store the answers, and the choice is about the direction of the work and the memory that it uses.
The last question in this topic shows the same problem in both styles.