Fibonacci Using DP in DSA Rust - Execution Trace

Concept Flow - Fibonacci Using DP

Start with n

↓

Create DP array of size n+1

↓

Set base cases: dp[0

↓

For i from 2 to n

↓

Calculate dp[i

↓

Return dp[n

We build a list to store Fibonacci numbers from 0 to n, starting with base cases, then fill each next number by adding the two before it.

Execution Sample

DSA Rust

fn fibonacci_dp(n: usize) -> usize {
    if n <= 1 {
        return n;
    }
    let mut dp = vec![0; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

This code calculates the nth Fibonacci number using a list to store all previous results.

Execution Table

Step	Operation	Index i	dp Array State	Calculation	Result at dp[i]
1	Initialize dp array	-	[0, 0, 0, 0, 0, 0]	-	-
2	Set base case dp[1]	1	[0, 1, 0, 0, 0, 0]	-	1
3	Calculate dp[2]	2	[0, 1, 0, 0, 0, 0]	dp[1] + dp[0] = 1 + 0	1
4	Calculate dp[3]	3	[0, 1, 1, 0, 0, 0]	dp[2] + dp[1] = 1 + 1	2
5	Calculate dp[4]	4	[0, 1, 1, 2, 0, 0]	dp[3] + dp[2] = 2 + 1	3
6	Calculate dp[5]	5	[0, 1, 1, 2, 3, 0]	dp[4] + dp[3] = 3 + 2	5
7	Return dp[5]	-	[0, 1, 1, 2, 3, 5]	-	5

💡 Reached n=5, dp array fully computed, returned dp[5]

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
dp	[0, 0, 0, 0, 0, 0]	[0, 1, 0, 0, 0, 0]	[0, 1, 1, 0, 0, 0]	[0, 1, 1, 2, 0, 0]	[0, 1, 1, 2, 3, 0]	[0, 1, 1, 2, 3, 5]	[0, 1, 1, 2, 3, 5]
i	-	1	2	3	4	5	-
dp[i]	-	1	1	2	3	5	-

Key Moments - 3 Insights

Why do we set dp[1] = 1 before the loop?

Because dp[1] is a base case for Fibonacci. Without setting it, dp[1] would be 0, causing wrong sums in later steps (see Step 2 in execution_table).

Why does the loop start from i = 2?

Because dp[0] and dp[1] are base cases already known. We start from 2 to build new values using previous two (see Steps 3 to 6).

What happens if n is 0 or 1?

For n=0, dp[0] = 0 is returned immediately. For n=1, dp[1] = 1 is returned. The loop does not run in these cases.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of dp[3]?

A 1

B 2

C 3

D 5

💡 Hint

Check the 'Result at dp[i]' column for Step 4 in execution_table.

At which step does dp[4] get its value calculated?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Index i' and 'Operation' columns in execution_table to find when dp[4] is updated.

If we change dp[1] to 2 at Step 2, what would dp[2] be at Step 3?

A 2

B 1

C 3

D 4

💡 Hint

dp[2] = dp[1] + dp[0], so changing dp[1] affects dp[2] directly (see Step 3 calculation).

Concept Snapshot

Fibonacci Using DP:
- Create dp array size n+1
- Set dp[0]=0, dp[1]=1 base cases
- For i=2 to n: dp[i] = dp[i-1] + dp[i-2]
- Return dp[n]
This avoids repeated calculations by storing results.

Full Transcript

This visualization shows how to calculate Fibonacci numbers using dynamic programming. We start by creating an array dp to hold Fibonacci values from 0 to n. We set the first two values dp[0]=0 and dp[1]=1 as base cases. Then, for each index i from 2 to n, we calculate dp[i] by adding the two previous values dp[i-1] and dp[i-2]. This way, each Fibonacci number is computed once and stored, avoiding repeated work. The execution table traces each step, showing how dp array changes and how each dp[i] is computed. Key moments clarify why base cases are set before the loop and why the loop starts at 2. The quiz tests understanding of dp values at specific steps and effects of changing base cases.

Practice

1. What is the main advantage of using dynamic programming (DP) to calculate Fibonacci numbers compared to a simple recursive approach?

easy

A. It avoids repeated calculations by storing intermediate results.

B. It uses less memory by not storing any results.

C. It calculates Fibonacci numbers using only recursion without loops.

D. It always runs in constant time regardless of input size.

Solution

1. Step 1: Understand recursive Fibonacci inefficiency

   Simple recursion recalculates the same Fibonacci values many times, causing exponential time complexity.

2. Step 2: How DP improves calculation

   DP stores intermediate Fibonacci values in a table (memoization or tabulation), so each value is computed once.

3. Final Answer:

   It avoids repeated calculations by storing intermediate results. -> Option A

4. Quick Check:

   DP stores results to avoid repeats [OK]

Hint: DP saves previous results to speed up Fibonacci [OK]

Common Mistakes:

• Thinking DP uses no extra memory
• Believing DP always runs in constant time
• Confusing recursion with DP

2. Which of the following Rust code snippets correctly initializes a vector to store Fibonacci numbers for dynamic programming?

easy

A. let fib = vec![0; n];

B. let mut fib = vec![0; n+1];

C. let mut fib = Vec::new();

D. let fib = [0; n+1];

Solution

1. Step 1: Check vector size for DP storage

   We need a vector of size n+1 to store Fibonacci numbers from 0 to n.

2. Step 2: Verify mutability and initialization

   Vector must be mutable to update values; initialized with zeros for all positions.

3. Final Answer:

   let mut fib = vec![0; n+1]; -> Option B

4. Quick Check:

   Mutable vector with n+1 zeros [OK]

Hint: Use mutable vector with size n+1 for DP array [OK]

Common Mistakes:

• Using immutable vector when updates needed
• Incorrect vector size causing index errors
• Using fixed-size array without mutability

3. What will be the output of the following Rust code that uses bottom-up DP to compute Fibonacci numbers?

fn fib(n: usize) -> usize {
    let mut dp = vec![0; n+1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i-1] + dp[i-2];
    }
    dp[n]
}

fn main() {
    println!("{}", fib(5));
}

medium

A. 13

B. 8

C. 5

D. 3

Solution

1. Step 1: Trace DP array filling for n=5

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Return dp[5]

   Function returns dp[5], which is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Bottom-up DP sums previous two values [OK]

Common Mistakes:

• Confusing index starting points
• Off-by-one errors in loop range
• Misreading dp array values

4. Identify the error in this Rust code for Fibonacci using DP and select the correct fix:

fn fib(n: usize) -> usize {
    let mut dp = vec![0; n];
    dp[0] = 0;
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i-1] + dp[i-2];
    }
    dp[n]
}

medium

A. Change vector size to n+1 and return dp[n]

B. Change vector size to n and return dp[n-1]

C. Initialize dp with zeros and ones alternatively

D. Remove dp[0] assignment since it's zero by default

Solution

1. Step 1: Check vector size and indexing

   Vector size is n (indices 0 to n-1), but loop 2..=n and dp[n] access index n, causing out of bounds panic.

2. Step 2: Fix vector size

   Change to vec![0; n+1] to store values up to index n.

3. Final Answer:

   Change vector size to n+1 and return dp[n] -> Option A

4. Quick Check:

   Size n+1 for indices 0 to n [OK]

Hint: Vector of size n+1 stores fib[0..n] [OK]

Common Mistakes:

• Accessing dp[n] causing panic
• Incorrect vector size for indexing
• Ignoring zero-based indexing

5. You want to compute the 10th Fibonacci number using top-down DP (memoization) in Rust. Which code snippet correctly implements memoization to avoid repeated calculations?

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

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

hard

A. Incorrect because base case should return 0 for n=1

B. Incorrect because memo vector should store usize, not Option<usize>

C. Incorrect because memo is not passed as mutable reference

D. Correct implementation of top-down DP with memoization

Solution

1. Step 1: Check memo vector type and initialization

   Memo uses Option<usize> to track computed values; initialized with None for all indices.

2. Step 2: Verify memoization logic

   Function returns stored value if present; otherwise computes recursively and stores result.

3. Step 3: Confirm base case correctness

   Returns n for n=0 or 1, which matches Fibonacci definition.

4. Final Answer:

   Correct implementation of top-down DP with memoization -> Option D

5. Quick Check:

   Memo stores Option, uses recursion with caching [OK]

Hint: Use Option to track computed Fibonacci values [OK]

Common Mistakes:

• Using usize vector without Option causes wrong caching
• Wrong base case returns
• Not passing memo as mutable reference