Memoization Top Down DP in DSA Python - 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 dynamic programming?

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 starting from the smallest, building up to the final solution.

beginner

In memoization, what data structure is commonly used to store intermediate results?

A dictionary or array is commonly used to store intermediate results (memo) so that repeated calls with the same inputs can return the stored result immediately.

intermediate

Why is memoization useful in recursive algorithms?

Memoization prevents the exponential explosion of recursive calls by saving results of subproblems, turning an exponential time algorithm into a polynomial time one.

beginner

What is the base case in a top-down DP recursive function?

The base case is the simplest subproblem that can be solved directly without recursion, often returning a fixed value to stop further recursive calls.

What does memoization primarily help to avoid in recursive functions?

A Repeated calculations of the same subproblems

B Using too much memory

C Writing iterative loops

D Sorting data

Memoization stores results of subproblems to avoid recalculating them, improving efficiency.

Which data structure is commonly used to implement memoization in Python?

A List or dictionary

B Queue

C Stack

D Set

Lists or dictionaries are used to store computed results for quick lookup.

In top-down DP, what triggers the recursive calls?

A Sorting the input

B Breaking the problem into smaller subproblems

C Iterating over all elements

D Using loops only

Top-down DP solves the problem by recursively breaking it into smaller subproblems.

What is the main difference between memoization and tabulation?

A Memoization uses loops; tabulation uses recursion

B Memoization uses less memory than tabulation

C Memoization is top-down recursion; tabulation is bottom-up iteration

D Tabulation is slower than memoization

Memoization uses recursion with caching, tabulation uses iterative filling of a table.

Which of the following is a good example problem to solve using memoization?

A Printing a string

B Sorting an array

C Finding maximum in an array

D Fibonacci sequence calculation

Fibonacci sequence has overlapping subproblems, making it ideal for memoization.

Explain how memoization improves the efficiency of a recursive Fibonacci function.

Think about how many times the same Fibonacci number is calculated without memoization.

Describe the steps to convert a naive recursive solution into a top-down DP solution using memoization.

Focus on caching results to avoid repeated work.

Practice

1. What is the main purpose of memoization in top-down dynamic programming?

easy

A. To store results of subproblems to avoid repeated calculations

B. To sort the input data before processing

C. To convert recursive code into iterative code

D. To increase the size of the input for better accuracy

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of subproblems so they are not recalculated multiple times.

2. Step 2: Compare options

   Only To store results of subproblems to avoid repeated calculations describes this purpose correctly. Other options describe unrelated actions.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option A

4. Quick Check:

   Memoization = Store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting or iteration
• Thinking memoization increases input size
• Believing memoization converts recursion to iteration

2. Which of the following is the correct way to define a memo dictionary in Python for top-down DP?

easy

A. memo = []

B. memo = {}

C. memo = set()

D. memo = ()

Solution

1. Step 1: Identify data structure for memo

   Memoization requires a dictionary to store key-value pairs of subproblem inputs and results.

2. Step 2: Match with options

   Only memo = {} uses a dictionary ({}). Lists, sets, and tuples do not support key-value storage.

3. Final Answer:

   memo = {} -> Option B

4. Quick Check:

   Memo dictionary = {} [OK]

Hint: Use {} for memo dictionary in Python [OK]

Common Mistakes:

• Using list or set instead of dictionary
• Confusing tuple with dictionary
• Not initializing memo before recursion

3. What will be the output of the following code?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 3

B. 8

C. 5

D. Error

Solution

1. Step 1: Understand Fibonacci calculation with memo

   fib(5) calculates Fibonacci number at position 5 using memo to save results.

2. Step 2: Calculate fib(5)

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Fibonacci(5) = 5 using memoized recursion [OK]

Common Mistakes:

• Confusing Fibonacci sequence values
• Expecting 8 instead of 5 for fib(5)
• Thinking code causes error due to default dict

4. Identify the error in this memoized Fibonacci function:

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

medium

A. Missing base case for n=0

B. Function lacks return statement

C. Memo dictionary is not used correctly

D. Default mutable argument causes shared state across calls

Solution

1. Step 1: Analyze default argument usage

   Using memo={} as default argument creates shared dictionary across calls, causing unexpected behavior.

2. Step 2: Identify correct practice

   Default mutable arguments should be avoided; better to use None and initialize inside function.

3. Final Answer:

   Default mutable argument causes shared state across calls -> Option D

4. Quick Check:

   Mutable default argument = bug [OK]

Hint: Avoid mutable default args like {} in function definitions [OK]

Common Mistakes:

• Ignoring mutable default argument issue
• Thinking base case is missing
• Assuming memo dictionary usage is wrong

5. You want to find the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Which memoized top-down function correctly solves this problem?

hard

A. def climb(n, memo=None):
if memo is None:
memo = {}
if n < 0:
return 0
if n == 0:
return 1
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

B. def climb(n):
if n <= 1:
return n
return climb(n-1) + climb(n-2)

C. def climb(n, memo={}):
if n == 0:
return 0
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

D. def climb(n, memo=None):
if memo is None:
memo = []
if n <= 1:
return 1
if n in memo:
return memo[n]
memo[n] = climb(n-1, memo) + climb(n-2, memo)
return memo[n]

Solution

1. Step 1: Understand problem and base cases

   Number of ways to climb n steps with 1 or 2 steps is classic DP with base cases: ways(0)=1, ways(-1)=0.

2. Step 2: Check each option for correctness

   def climb(n, memo=None): if memo is None: memo = {} if n < 0: return 0 if n == 0: return 1 if n in memo: return memo[n] memo[n] = climb(n-1, memo) + climb(n-2, memo) return memo[n] correctly initializes memo, handles negative and zero cases, and uses memoization properly. Others have wrong base cases or memo usage.

3. Final Answer:

   Option A function correctly solves the problem -> Option A

4. Quick Check:

   Proper base cases + memo dict = correct solution [OK]

Hint: Base cases and memo dict initialization are key [OK]

Common Mistakes:

• Wrong base case returns
• Using mutable default memo argument
• Using list instead of dict for memo