Memoization

Abstract

---

• An optimisation technique used in Dynamic Programming, used in both Top-down DP Approach and Bottom-up DP Approach
• The technique stores the results of expensive function calls and return the cached result in $O(1)$ 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.

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