Overlapping Subproblems and Optimal Substructure in DSA Rust - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Start Problem

↓

Check if solution known?

Yes→Use stored solution

No↓

Divide problem into subproblems

↓

Recursively solve subproblems

↓

Combine subproblem solutions

↓

Store solution for reuse

↓

Return solution

↓

End

This flow shows how a problem is broken into smaller parts, solved recursively, and solutions are saved to avoid repeating work.

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 result = fib(n-1, memo) + fib(n-2, memo);
    memo[n] = Some(result);
    result
}

This Rust function calculates Fibonacci numbers using memoization to reuse previously computed results.

Execution Table

Step	Operation	n	Memo Before	Memo After	Returned Value	Visual State
1	Call fib(4)	4	[None, None, None, None, None]	[None, None, None, None, None]	?	fib(4) called, memo empty
2	Call fib(3)	3	[None, None, None, None, None]	[None, None, None, None, None]	?	fib(3) called, memo empty
3	Call fib(2)	2	[None, None, None, None, None]	[None, None, None, None, None]	?	fib(2) called, memo empty
4	Call fib(1)	1	[None, None, None, None, None]	[None, None, None, None, None]	1	fib(1) base case returns 1
5	Call fib(0)	0	[None, None, None, None, None]	[None, None, None, None, None]	0	fib(0) base case returns 0
6	Compute fib(2)	2	[None, None, None, None, None]	[None, None, Some(1), None, None]	1	fib(2) = 1 stored in memo[2]
7	Call fib(1)	1	[None, None, Some(1), None, None]	[None, None, Some(1), None, None]	1	fib(1) base case returns 1
8	Compute fib(3)	3	[None, None, Some(1), None, None]	[None, None, Some(1), Some(2), None]	2	fib(3) = 2 stored in memo[3]
9	Call fib(2)	2	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), None]	1	fib(2) memo hit returns 1
10	Compute fib(4)	4	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), Some(3)]	3	fib(4) = 3 stored in memo[4]
11	Return fib(4)	4	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]	3	Final result returned

💡 fib(4) computed using stored subproblem results, recursion ends

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	?	1	2	3	3

Key Moments - 3 Insights

Why does fib(2) get computed only once?

Because after the first computation at step 6, fib(2) is stored in memo[2]. Later calls (step 9) find this stored value and reuse it, avoiding repeated work.

What happens when the function hits the base case?

At steps 4 and 5, when n is 1 or 0, the function returns immediately without recursion, providing the simplest known answers.

How does memoization help in this example?

Memoization saves results of subproblems (like fib(2), fib(3)) so that when these are needed again, the function returns the stored value instantly, reducing repeated calculations as seen in step 9.

Visual Quiz - 3 Questions

Look at the execution table, what is the value returned by fib(3) at step 8?

A 2

B 3

C 1

D Undefined

💡 Hint

Check the 'Returned Value' column at step 8 in the execution_table.

At which step does the memo first store a computed Fibonacci value?

A Step 8

B Step 4

C Step 6

D Step 10

💡 Hint

Look at the 'Memo After' column to see when Some(value) first appears.

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

A Calls would decrease

B Calls would increase

C Calls would stay the same

D Calls would be zero

💡 Hint

Refer to the concept of overlapping subproblems and how memoization avoids repeated calls.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems
- Solve subproblems recursively
- Store results (memoization) to reuse
- Avoid repeated work (overlapping subproblems)
- Combine subproblem solutions for final answer

Full Transcript

This concept shows how some problems can be split into smaller parts that overlap. Instead of solving the same part many times, we save answers in a memo. The example uses Fibonacci numbers where fib(n) depends on fib(n-1) and fib(n-2). The code checks if the answer is already known; if yes, it returns it immediately. If not, it computes, stores, and returns it. This saves time and avoids repeated calculations, making the solution efficient.

Practice

1. Which of the following best describes the overlapping subproblems property in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems that are solved multiple times.

B. The problem has a unique solution without repeating any subproblems.

C. The problem requires sorting before solving.

D. The problem can only be solved using recursion without memoization.

Solution

1. Step 1: Understand overlapping subproblems

   Overlapping subproblems means the same smaller problems appear multiple times during solving.

2. Step 2: Match definition to options

   The problem can be broken down into smaller subproblems that are solved multiple times. correctly states that subproblems repeat and can be reused to save time.

3. Final Answer:

   The problem can be broken down into smaller subproblems that are solved multiple times. -> Option A

4. Quick Check:

   Overlapping subproblems = repeated smaller problems [OK]

Hint: Look for repeated smaller problems solved multiple times [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking sorting is required for overlapping subproblems
• Assuming recursion alone solves overlapping subproblems

2. Which Rust syntax correctly declares a function to compute Fibonacci numbers using memoization?

easy

A. fn fib(n: usize, memo: &Vec<usize>) -> usize { ... }

B. fn fib(n: usize) -> usize { let memo = Vec::new(); ... }

C. fn fib(n: usize, memo: Vec<usize>) -> usize { ... }

D. fn fib(n: usize, memo: &mut Vec) -> usize { ... }

Solution

1. Step 1: Identify correct parameter passing for memo

   Memo must be mutable reference to allow updates during recursion.

2. Step 2: Check options for mutable reference

   fn fib(n: usize, memo: &mut Vec) -> usize { ... } uses &mut Vec, which allows updating memo inside the function.

3. Final Answer:

   fn fib(n: usize, memo: &mut Vec) -> usize { ... } -> Option D

4. Quick Check:

   Mutable reference needed for memo updates [OK]

Hint: Use &mut for mutable references in Rust function parameters [OK]

Common Mistakes:

• Passing memo by value causing copies
• Using immutable reference &Vec which disallows updates
• Initializing memo inside function losing previous results

3. What is the output of this Rust code that uses memoization for Fibonacci?

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

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

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Trace fib(5) calls with memo

   fib(5) = fib(4) + fib(3), fib(4) = 3, fib(3) = 2, so fib(5) = 5.

2. Step 2: Confirm memo stores results to avoid recomputation

   Memoization stores fib(3)=2, fib(4)=3, so final fib(5) = 5 is returned and printed.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Miscounting base cases

4. Identify the bug in this Rust code for Fibonacci with memoization:

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

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

medium

A. Vector size is too small causing index out of bounds

B. Memo is not mutable

C. Base case condition is incorrect

D. Using unwrap() causes panic always

Solution

1. Step 1: Check vector size for memo

   Memo vector has size 5 but fib(5) accesses memo[5], which is out of bounds.

2. Step 2: Understand Rust vector indexing

   Indexing beyond vector length causes runtime panic, so vector size must be at least n+1.

3. Final Answer:

   Vector size is too small causing index out of bounds -> Option A

4. Quick Check:

   Memo size < n+1 causes index error [OK]

Hint: Ensure memo vector size is n+1 for fib(n) [OK]

Common Mistakes:

• Not allocating enough space for memo
• Ignoring Rust's zero-based indexing
• Assuming unwrap() always safe

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. Which property allows using dynamic programming to solve this efficiently?

hard

A. Greedy choice: always pick the cell with the smallest immediate cost.

B. Overlapping subproblems: each cell's cost is unique and never reused.

C. Optimal substructure: the minimum cost path to a cell depends on minimum cost paths to adjacent cells.

D. Divide and conquer: split the grid into independent parts solved separately.

Solution

1. Step 1: Understand minimum cost path problem

   The cost to reach a cell depends on the best path to its neighbors (top or left).

2. Step 2: Identify optimal substructure property

   Optimal substructure means the optimal solution to the whole problem contains optimal solutions to subproblems.

3. Final Answer:

   Optimal substructure: the minimum cost path to a cell depends on minimum cost paths to adjacent cells. -> Option C

4. Quick Check:

   Minimum cost path uses optimal substructure [OK]

Hint: Look for solutions built from optimal subproblems [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Assuming greedy always works here
• Thinking divide and conquer applies without overlap