Memoization Top Down DP in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of dynamic programming?

Memoization is a technique where we store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

intermediate

How does top-down dynamic programming differ from bottom-up?

Top-down DP uses recursion with memoization to solve problems by breaking them into smaller subproblems and storing results. Bottom-up DP solves subproblems iteratively from smallest to largest without recursion.

beginner

In TypeScript, how can you implement memoization for a Fibonacci function?

You can use a Map or object to store computed Fibonacci values. Before computing a value, check if it exists in the map. If yes, return it; if no, compute and store it.

intermediate

Why is memoization useful in recursive algorithms?

Memoization prevents repeated calculations of the same subproblems, reducing exponential time complexity to polynomial time, making recursive algorithms efficient.

intermediate

What is a common mistake when implementing memoization in top-down DP?

A common mistake is not storing the result before returning it, which causes repeated calculations and defeats memoization's purpose.

What does memoization store to optimize recursive calls?

A All function calls

B Input parameters only

C Random values

D Results of subproblems

Memoization stores the results of subproblems to avoid recalculating them.

Which data structure is commonly used in TypeScript for memoization?

A Array only

B Map or object

C Set

D Queue

Map or object is used to store computed results with keys as input parameters.

Top-down DP with memoization is best described as:

A Iterative with caching

B Iterative without caching

C Recursive with caching

D Recursive without caching

Top-down DP uses recursion and caches results to avoid repeated work.

What happens if you forget to store results in memoization?

A The algorithm runs slower due to repeated calculations

B The algorithm runs faster

C The algorithm crashes

D The algorithm uses less memory

Without storing results, repeated calculations happen, slowing down the algorithm.

Memoization changes the time complexity of naive recursion from:

A Exponential to polynomial

B Polynomial to exponential

C Linear to exponential

D Constant to linear

Memoization reduces exponential time complexity to polynomial by caching results.

Explain how memoization works in top-down dynamic programming with an example.

Think about how you avoid repeating the same calculation.

Describe the benefits and potential pitfalls of using memoization in recursive algorithms.

Consider both speed and memory trade-offs.