What is the primary purpose of memoization in Dynamic Programming?
2024
What is the primary purpose of memoization in Dynamic Programming?
- A.
To reduce memory allocation during execution
- B.
To store intermediate results of repeated subproblems
- C.
To increase recursion depth in algorithms
- D.
To execute multiple functions simultaneously
- E.
To convert iterative solutions into recursive solutions
Attempted by 34 students.
Show answer & explanation
Correct answer: B
Correct answer: To store intermediate results of repeated subproblems.
Memoization is the top-down optimisation technique used in Dynamic Programming. A recursive solution often solves the same overlapping subproblem many times, which wastes computation. Memoization fixes this by caching (storing) the result of each subproblem the first time it is computed, usually in an array or a hash map.
On every recursive call the algorithm first checks the cache: if the subproblem's result is already stored, it is returned immediately instead of being recomputed; otherwise the subproblem is solved once and its result is saved for future use.
This turns an exponential-time recursion (for example, naive Fibonacci) into a polynomial-time solution, because each distinct subproblem is evaluated only once. Hence the primary purpose of memoization is to store the intermediate results of repeated (overlapping) subproblems so they are not recomputed.