Dynamic Programming Questions Medium
Memoization and tabulation are two common techniques used in dynamic programming to optimize the computation of subproblems. The main difference between them lies in the way they store and retrieve the computed values.
1. Memoization:
Memoization is a top-down approach where the problem is divided into smaller subproblems, and the solutions to these subproblems are stored in a memoization table or cache. When a subproblem needs to be solved, the algorithm first checks if the solution is already present in the cache. If it is, the stored value is directly returned; otherwise, the subproblem is solved and the solution is stored in the cache for future use. This technique ensures that each subproblem is solved only once, avoiding redundant computations.
2. Tabulation:
Tabulation is a bottom-up approach where the problem is solved by iteratively building the solutions to smaller subproblems and storing them in a table or array. The algorithm starts with the base cases and then iteratively computes the solutions for larger subproblems until the final solution is obtained. In tabulation, there is no need for recursion or memoization as the solutions are computed in a systematic manner. The final solution is obtained by accessing the value stored in the last cell of the table.
In summary, the main difference between memoization and tabulation is the way they store and retrieve the computed values. Memoization uses a cache to store solutions to subproblems, while tabulation uses a table or array to store solutions in a bottom-up manner. Both techniques aim to optimize the computation of subproblems in dynamic programming, but they differ in their implementation approach.