Memoization Top Down DP in DSA Python

Mental Model

Remember answers to small problems so you don't solve them again.

Analogy: Like writing down answers to tricky homework questions so you can check them later instead of redoing the work.

Problem -> Break into smaller problems -> Solve smaller problems -> Store answers in a box (cache) -> Use stored answers when needed

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using memoization

Goal: Find the 5th Fibonacci number efficiently by storing intermediate results

Step 1: Call fib(5), no cached answer, so compute fib(4) and fib(3)

Cache: {}

Why: We start solving the big problem by breaking it into smaller ones

Step 2: Call fib(4), no cached answer, so compute fib(3) and fib(2)

Cache: {}

Why: Keep breaking down until base cases

Step 3: Call fib(3), no cached answer, so compute fib(2) and fib(1)

Cache: {}

Why: Continue breaking down

Step 4: Call fib(2), no cached answer, so compute fib(1) and fib(0)

Cache: {}

Why: Keep going until base cases

Step 5: fib(1) and fib(0) are base cases, return 1 and 0 respectively

Cache: {}

Why: Base cases give direct answers

Step 6: Calculate fib(2) = fib(1) + fib(0) = 1 + 0 = 1, store in cache

Cache: {2: 1}

Why: Store result to avoid recomputing

Step 7: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store in cache

Cache: {2: 1, 3: 2}

Why: Use cached fib(2) and base fib(1), store result

Step 8: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in cache

Cache: {2: 1, 3: 2, 4: 3}

Why: Use cached fib(3) and fib(2), store result

Step 9: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store in cache

Cache: {2: 1, 3: 2, 4: 3, 5: 5}

Why: Use cached fib(4) and fib(3), store result

Result:

Cache: {2: 1, 3: 2, 4: 3, 5: 5}
Answer: 5

Annotated Code

DSA Python

class Fibonacci:
    def __init__(self):
        self.cache = {}

    def fib(self, n: int) -> int:
        if n in self.cache:
            return self.cache[n]  # return cached answer
        if n <= 1:
            return n  # base case
        # compute fib(n-1) and fib(n-2) recursively
        result = self.fib(n - 1) + self.fib(n - 2)
        self.cache[n] = result  # store in cache
        return result

# Driver code
fib_calc = Fibonacci()
print(fib_calc.fib(5))

if n in self.cache:

Check if answer already computed to avoid repeated work

if n <= 1:

Return base case directly

result = self.fib(n - 1) + self.fib(n - 2)

Break problem into smaller subproblems

self.cache[n] = result

Save computed answer for future use

Output

5

Complexity Analysis

Time: O(n) because each number from 0 to n is computed once and stored

Space: O(n) because cache stores results for each number up to n

vs Alternative: Without memoization, time is O(2^n) due to repeated calculations; memoization reduces it to O(n)

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Python

if n <= 1:

n = 1

Returns 1 immediately as base case

DSA Python

if n <= 1:

Repeated calls with same n

Returns cached result instantly without recomputation

DSA Python

if n in self.cache:

When to Use This Pattern

When a problem can be broken into overlapping smaller problems and you want to avoid repeating work, use memoization top down DP to store and reuse answers.

Common Mistakes

Mistake: Not storing the computed result in cache after calculation
Fix: Add cache assignment after computing result: self.cache[n] = result

Mistake: Not checking cache before recursive calls
Fix: Add a check at the start: if n in self.cache: return cached value

Summary

Stores answers to smaller problems to avoid repeated work in recursion.

Use when a problem has overlapping subproblems and you want to speed up recursion.

The key is to remember and reuse answers instead of recalculating them.

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