Memoization Top Down DP in DSA Rust - 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

↓

End

The process starts by checking if the answer is already saved. If yes, return it. If no, compute it recursively, save it, then return.

Execution Sample

DSA Rust

fn fib(n: usize, memo: &mut Vec<Option<usize>>) -> usize {
    if let Some(val) = memo[n] {
        return val;
    }
    if n <= 1 {
        return n;
    }
    let res = fib(n-1, memo) + fib(n-2, memo);
    memo[n] = Some(res);
    res
}

Calculates Fibonacci number n using top-down memoization to avoid repeated work.

Execution Table

Step	Operation	n	Memo Before	Recursive Calls	Memo After	Returned Value
1	Call fib(4)	4	[None, None, None, None, None]	fib(3), fib(2)	[None, None, None, None, None]	pending
2	Call fib(3)	3	[None, None, None, None, None]	fib(2), fib(1)	[None, None, None, None, None]	pending
3	Call fib(2)	2	[None, None, None, None, None]	fib(1), fib(0)	[None, None, None, None, None]	pending
4	Call fib(1)	1	[None, None, None, None, None]	none	[None, None, None, None, None]	1
5	Call fib(0)	0	[None, None, None, None, None]	none	[None, None, None, None, None]	0
6	Compute fib(2)	2	[None, None, None, None, None]	fib(1)=1 + fib(0)=0	[None, None, Some(1), None, None]	1
7	Call fib(1)	1	[None, None, Some(1), None, None]	none	[None, None, Some(1), None, None]	1
8	Compute fib(3)	3	[None, None, Some(1), None, None]	fib(2)=1 + fib(1)=1	[None, None, Some(1), Some(2), None]	2
9	Call fib(2)	2	[None, None, Some(1), Some(2), None]	memo hit	[None, None, Some(1), Some(2), None]	1
10	Compute fib(4)	4	[None, None, Some(1), Some(2), None]	fib(3)=2 + fib(2)=1	[None, None, Some(1), Some(2), Some(3)]	3
11	Return final result	4	[None, None, Some(1), Some(2), Some(3)]	none	[None, None, Some(1), Some(2), Some(3)]	3

💡 All recursive calls resolved and results stored in memo, final fib(4) = 3 returned.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	[None, None, None, None, None]	[None, None, Some(1), None, None]	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

Why do we check memo before computing fib(n)?

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

What happens if n is 0 or 1?

Base cases (Steps 4 and 5) return n directly without recursion, stopping infinite calls.

How does memoization improve performance here?

Memo stores results of fib for each n (Steps 6, 8, 10), so repeated calls reuse these values instead of recalculating.

Visual Quiz - 3 Questions

Look at the execution table at Step 6, what value is stored in memo[2] after computing fib(2)?

A None

B Some(2)

C Some(1)

D Some(3)

💡 Hint

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

At which step does the function first return a value without further recursive calls?

A Step 1

B Step 4

C Step 6

D Step 9

💡 Hint

Look for steps where 'Recursive Calls' is 'none' and a value is returned.

If memo was not used, how would the number of recursive calls change?

A They would increase significantly

B They would decrease

C They would stay the same

D They would be zero

💡 Hint

Refer to the 'Recursive Calls' column showing repeated calls avoided by memoization.

Concept Snapshot

Memoization Top Down DP:
- Use recursion with a memo table to save results.
- Check memo before computing to avoid repeats.
- Store computed results in memo.
- Base cases return directly.
- Improves performance by caching.
- Common in Fibonacci and similar problems.

Full Transcript

Memoization in top-down dynamic programming means saving results of recursive calls in a memo table. When the function is called with a value n, it first checks if the result is already in memo. If yes, it returns that result immediately, avoiding repeated work. If not, it computes the result recursively, stores it in memo, and returns it. Base cases like n=0 or n=1 return directly without recursion. This approach greatly reduces the number of recursive calls, improving performance. The example traced is Fibonacci calculation for n=4, showing how memo fills step-by-step and results are reused.

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 reduce memory usage by deleting variables

Solution

1. Step 1: Understand memoization role

   Memoization saves 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. Sorting, converting recursion, or deleting variables are unrelated.

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
• Thinking memoization reduces memory by deleting data
• Believing memoization changes recursion to iteration

2. Which of the following Rust code snippets correctly declares a memoization cache for a function with input type usize and output type usize?

easy

A. let memo: Vec<usize> = Vec::new();

B. let memo = HashMap::new();

C. let mut memo: Vec = vec![None; n + 1];

D. let mut memo: Vec<usize> = vec![0; n];

Solution

1. Step 1: Identify correct memo type

   Memoization cache should store Option<usize> to mark computed or not, initialized with None.

2. Step 2: Check each option

   let mut memo: Vec = vec![None; n + 1]; uses Vec with None values, correct for memoization. let memo = HashMap::new(); is a HashMap but missing mut and initialization syntax. let memo: Vec<usize> = Vec::new(); lacks Option type. let mut memo: Vec<usize> = vec![0; n]; uses usize with zeros, which can't distinguish computed or not.

3. Final Answer:

   let mut memo: Vec = vec![None; n + 1]; -> Option C

4. Quick Check:

   Memo cache = Vec with None [OK]

Hint: Use Option type to mark uncomputed states [OK]

Common Mistakes:

• Using Vec<usize> without Option to track computed
• Not making memo mutable
• Incorrect initialization of HashMap

3. Consider this Rust function using memoization to compute Fibonacci numbers:

fn fib(n: usize, memo: &mut Vec) -> usize {
    if n <= 1 {
        return n;
    }
    if let Some(val) = memo[n] {
        return val;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = Some(result);
    result
}

fn main() {
    let n = 5;
    let mut memo = vec![None; n + 1];
    println!("{}", fib(n, &mut memo));
}

What is the output when this code runs?

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation

   fib(5) = fib(4) + fib(3). Calculating recursively with memoization avoids repeated work.

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 B

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting zero-based indexing
• Ignoring memoization effect

4. This Rust code tries to memoize the factorial function but has a bug:

fn fact(n: usize, memo: &mut Vec) -> usize {
    if n == 0 {
        return 1;
    }
    if memo[n].is_some() {
        return memo[n].unwrap();
    }
    let result = n * fact(n - 1, memo);
    memo[n] = Some(result);
    result
}

fn main() {
    let n = 5;
    let mut memo = vec![None; n];
    println!("{}", fact(n, &mut memo));
}

What is the bug causing a runtime error?

medium

A. The memo vector size is too small causing index out of bounds

B. The base case should return 0 instead of 1

C. The function does not update memo correctly

D. The function should not use recursion

Solution

1. Step 1: Check memo vector size

   Memo is created with size n (5), but fact accesses memo[n], which is memo[5], out of bounds since indices go 0 to 4.

2. Step 2: Identify cause of runtime error

   Accessing memo[5] causes panic due to index out of bounds. The vector should be size n+1 to include index 5.

3. Final Answer:

   The memo vector size is too small causing index out of bounds -> Option A

4. Quick Check:

   Vector size < needed index = runtime error [OK]

Hint: Memo size must cover all indices used [OK]

Common Mistakes:

• Ignoring vector size when indexing
• Changing base case incorrectly
• Thinking recursion is the problem

5. You want to use top-down memoization in Rust to count the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Which of these implementations correctly applies memoization to avoid repeated calculations?

fn climb(n: usize, memo: &mut Vec) -> usize {
    if n == 0 {
        return 1;
    }
    if n < 0 {
        return 0;
    }
    if let Some(val) = memo[n] {
        return val;
    }
    let ways = climb(n - 1, memo) + climb(n - 2, memo);
    memo[n] = Some(ways);
    ways
}

fn main() {
    let n = 4;
    let mut memo = vec![None; n + 1];
    println!("{}", climb(n, &mut memo));
}

hard

A. Incorrect because it does not handle negative indices safely

B. Incorrect because it uses iteration instead of recursion

C. Incorrect because memo vector is not mutable

D. Correct implementation with proper base cases and memo usage

Solution

1. Step 1: Check base cases and recursion

   Base cases handle n == 0 (1 way) and n < 0 (0 ways), which is correct for counting ways.

2. Step 2: Verify memoization usage

   Memo vector is mutable and stores Option<usize>. It checks memo[n] before recursion and stores result after calculation.

3. Step 3: Confirm no unsafe indexing

   Negative n returns 0 before indexing memo, so no out-of-bounds access.

4. Final Answer:

   Correct implementation with proper base cases and memo usage -> Option D

5. Quick Check:

   Base cases + memo check = correct memoization [OK]

Hint: Check base cases and memo before recursion [OK]

Common Mistakes:

• Not handling negative n before memo access
• Forgetting to make memo mutable
• Using iteration instead of recursion in top-down DP