Abstract
- A technique stores the results of expensive function calls and return the cached result in when the same function call is executed
Improves computation efficiency
With the cost of Main Memory, we avoid redundant expensive computations. This improve the overall running performance of the program.
Use case in dynamic programming
An optimisation technique used in Dynamic Programming, used in both Top-down DP Approach and Bottom-up DP Approach.
DP Table
- Memoization in Dynamic Programming to trade space for time - use extra space to hold optimal solution of Overlapping Subproblems (重复子问题) to avoid duplicated computation
- DP table can take the form of Array or simply a variable