Memoization Top Down DP in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of this code that calculates Fibonacci numbers using memoization?

DSA Python

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))

A 13

B 8

C 3

D 5

💡 Hint

Remember Fibonacci sequence starts with 0,1 and each next number is sum of previous two.

The Fibonacci sequence starts as 0,1,1,2,3,5,... So fib(5) is 5.

❓ Predict Output

intermediate

Output of Climbing Stairs Problem

What is the output of this memoized function that counts ways to climb stairs?

DSA Python

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

print(climb_stairs(4))

A 5

B 7

C 8

D 6

💡 Hint

Ways to climb 1 or 2 stairs are base cases.

Ways to climb 4 stairs = ways(3) + ways(2) = 3 + 2 = 5.

🔧 Debug

advanced

Identify the error in memoized factorial

What error does this code raise when called with factorial(5)?

DSA Python

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

print(factorial(5))

A No error, output is 120

B RecursionError: maximum recursion depth exceeded

C TypeError: factorial() missing 1 required positional argument: 'memo'

D NameError: name 'memo' is not defined

💡 Hint

Check how recursive calls pass the memo dictionary.

The recursive call factorial(n-1) misses the memo argument, causing TypeError.

❓ Predict Output

advanced

Output of Memoized Coin Change Ways

What is the output of this code that counts ways to make change using memoization?

DSA Python

def coin_change(coins, amount, memo={}):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    if amount in memo:
        return memo[amount]
    ways = 0
    for coin in coins:
        ways += coin_change(coins, amount - coin, memo)
    memo[amount] = ways
    return ways

print(coin_change([1,2], 3))

A 4

B 3

C 2

D 5

💡 Hint

Count all combinations of coins that sum to amount.

Ways to make 3 with coins 1 and 2 are: (1+1+1), (1+2), (2+1) = 3 ways.

🧠 Conceptual

expert

Memoization Cache Behavior in Recursive Calls

Consider a memoized recursive function with a mutable default argument for memo cache. What is the main risk of using a mutable default argument like memo={} in Python for memoization?

A The memo cache is shared across all calls, causing unexpected results in multiple calls.

B The memo cache is reset on every recursive call, causing no memoization effect.

C The function will raise a SyntaxError due to mutable default argument.

D The memo cache will only store the last computed value, losing previous results.

💡 Hint

Think about how default arguments behave in Python functions.

Mutable default arguments are created once and shared across calls, which can cause data from one call to affect another.

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