L20-21 (Memoization, more Dynamic Programming) Flashcards
1
Q
What’s the definition of Memoization
A
- Memoization is a technique used in dynamic programming and other algorithmic approaches to optimize the performance of a function with overlapping subproblems.
- It involves caching and reusing the results of expensive function calls to avoid redundant computations.
- Memoization is particularly useful in recursive algorithms where subproblems are repeatedly solved.
2
Q
How is Memoization implemented?
A
- Memoization can be implemented using a data structure, such as a hash table or an array, to store the results of function calls.
- This data structure, often called a memo or memoization table, maps input values to their corresponding outputs.
- When a function is called with a specific input, the memoization table is checked for a precomputed result. If the result is found, it is returned immediately; otherwise, the function is executed, and the result is stored in the memoization table for future use.
3
Q
Describe the difference between top-down and bottom-up DP
A
- Top-down dynamic programming (DP) with memoization involves solving the problem by breaking it into smaller subproblems and solving them recursively.
- Memoization is used to store the results of overlapping subproblems to avoid redundant computations.
- On the other hand, bottom-up DP is an iterative approach that solves the problem by building a solution from smaller subproblems to larger ones.
- While memoization is a characteristic of top-down DP, bottom-up DP does not require memoization as it directly fills the DP table in an organized manner.
4
Q
Discuss the pros and cons of memoization
A
Pros:
- Reduces time complexity by avoiding redundant computations.
- Can make a significant difference in the performance of recursive algorithms with overlapping subproblems.
- Often easier to implement than a bottom-up DP approach.
Cons:
- Increases space complexity due to the memoization table.
- May introduce the risk of stack overflow in deep recursion scenarios.