Memoization Top Down DP in DSA Python - Execution Trace

Concept Flow - Memoization Top Down DP

Start with problem input

↓

Check if result in memo?

Yes→Return memoized result

No↓

Compute result by recursive calls

↓

Store result in memo

↓

Return computed result

The flow shows checking memo before computing, then storing and returning results to avoid repeated work.

Execution Sample

DSA Python

def fib(n, memo=None):
    if memo is None:
        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]

This code computes Fibonacci numbers using top-down memoization to save results and avoid repeated calculations.

Execution Table

Step	Operation	Current n	Memo Before	Recursive Calls	Memo After	Returned Value
1	Call fib(4)	4	{}	fib(3), fib(2)	{}	pending
2	Call fib(3)	3	{}	fib(2), fib(1)	{}	pending
3	Call fib(2)	2	{}	fib(1), fib(0)	{}	pending
4	Call fib(1)	1	{}	none	{}	1
5	Call fib(0)	0	{}	none	{}	0
6	Compute fib(2)	2	{}	fib(1)=1, fib(0)=0	{2:1}	1
7	Call fib(1)	1	{2:1}	none	{2:1}	1
8	Compute fib(3)	3	{2:1}	fib(2)=1, fib(1)=1	{2:1, 3:2}	2
9	Call fib(2)	2	{2:1, 3:2}	none	{2:1, 3:2}	1
10	Compute fib(4)	4	{2:1, 3:2}	fib(3)=2, fib(2)=1	{2:1, 3:2, 4:3}	3
11	Return final result	4	{2:1, 3:2, 4:3}	none	{2:1, 3:2, 4:3}	3

💡 All recursive calls resolved and memo contains results for n=2,3,4; final fib(4) returned as 3

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	{}	{2:1}	{2:1, 3:2}	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

Why do we check if n is in memo before computing?

Checking memo first (see Step 2 and Step 9) avoids repeating expensive recursive calls by returning stored results immediately.

Why does the recursion stop at n <= 1?

At n=0 or n=1 (Step 4 and 5), the function returns base values directly, preventing infinite recursion and starting the memoization build-up.

How does memoization improve performance here?

Memo stores results after first computation (Step 6, 8, 10), so repeated calls like fib(2) reuse stored values (Step 9), reducing calls from exponential to linear.

Visual Quiz - 3 Questions

Look at the execution table, what is the memo content after Step 8?

A {2:1}

B {2:1, 3:2}

C {}

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

💡 Hint

Check the 'Memo After' column at Step 8 in the execution_table.

At which step does fib(2) return its computed value for the first time?

A Step 6

B Step 9

C Step 4

D Step 10

💡 Hint

Look for when fib(2) is computed and memo updated in the execution_table.

If memo was not used, how would the number of calls for fib(2) change?

A It would be called fewer times

B It would be called the same number of times

C It would be called more times

D It would never be called

💡 Hint

Refer to the memo usage in Steps 2, 3, 9 showing reuse of fib(2) result.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo dictionary
- Check memo before computing
- Store computed results in memo
- Avoid repeated work by returning memoized results
- Converts exponential recursion to linear time

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo dictionary. When the function is called with a value, it first checks if the result is already in memo. If yes, it returns that result immediately. If not, it computes the result recursively, stores it in memo, and returns it. This avoids repeated calculations and speeds up the program. For example, in Fibonacci, fib(2) is computed once and reused many times. The recursion stops at base cases n=0 or n=1. This technique changes exponential time to linear time by caching results.

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