Explain Memoization. How does it optimize recursive solutions?
Memoization
Memoization is a top-down dynamic programming technique that stores the results of previously computed subproblems so they do not need to be recalculated. It is particularly effective when a recursive algorithm has overlapping subproblems.
Without memoization, Fibonacci recursively recomputes the same values and has exponential time complexity. With memoization, each distinct subproblem is calculated once, reducing the time complexity to O(n), with O(n) additional space for the cache and recursion stack.
- 1
Memoization stores previously computed results.
- 2
It is commonly implemented using a hash map, object, or array.
- 3
It is useful for overlapping recursive subproblems.
- 4
It generally trades additional memory for improved execution time.
- 5
It is a top-down dynamic programming approach.
Follow-up Questions
- What is the difference between memoization and tabulation?
- When does memoization increase memory usage significantly?
- How can dynamic programming be derived from a recursive solution?