What is Tabulation?
Explore the concept of tabulation in bottom-up dynamic programming. Understand how solving smaller subproblems sequentially and storing their results in arrays helps build efficient solutions. Learn the differences between tabulation and memoization, and why order matters when constructing the solution.
We'll cover the following...
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. ...