Memoization Top Down DP in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the result is already computed in the memo dictionary.

DSA Python

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

Drag options to blanks, or click blank then click option'

Anot in

B==

Cin

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' or '!=' instead of 'in' to check dictionary keys.

Checking if n is not in memo instead of in memo.

We check if n is in memo to return the stored result and avoid recomputation.

2fill in blank

medium

Complete the code to store the computed Fibonacci value in the memo dictionary.

DSA Python

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting to add the two recursive calls.

Fibonacci numbers are calculated by adding the two previous numbers.

3fill in blank

hard

Fix the error in the base case to correctly return the Fibonacci number for n=0 or n=1.

DSA Python

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

Drag options to blanks, or click blank then click option'

A>=

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' which only checks for n == 1, missing n == 0.

Using '>' or '>=' which are incorrect for base case.

The base case should cover n equal to 0 or 1, so use '<=' to include both.

4fill in blank

hard

Fill both blanks to complete the memoized factorial function.

DSA Python

def factorial(n, memo={}):
    if n == 0:
        return 1
    if n [1] memo:
        return memo[n]
    memo[n] = n [2] factorial(n-1, memo)
    return memo[n]

Drag options to blanks, or click blank then click option'

Ain

B*

C+

Dnot in

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '*' for multiplication.

Checking if n is not in memo instead of in memo.

Check if n is in memo to reuse result, and multiply n by factorial(n-1).

5fill in blank

hard

Fill all three blanks to complete the memoized function that counts ways to climb stairs.

DSA Python

def climb_stairs(n, memo={}):
    if n <= 1:
        return 1
    if n [1] memo:
        return memo[n]
    memo[n] = climb_stairs(n-1, memo) [2] climb_stairs(n-2, memo)
    return memo[[3]]

Drag options to blanks, or click blank then click option'

Ain

B+

Cn

Dnot in

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'not in' instead of 'in' for memo check.

Using '-' or '*' instead of '+' for adding ways.

Returning memo with wrong key.

Check if n is in memo, add results of n-1 and n-2 steps, and return memo[n].

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