Fibonacci Using DP in DSA Go - Execution Trace

Concept Flow - Fibonacci Using DP

Start with base cases

↓

Initialize DP array with base values

↓

For each i from 2 to n

↓

Calculate dp[i

↓

Store result in dp array

↓

Return dp[n

Start with base Fibonacci values, then fill the dp array step-by-step by adding the two previous values until reaching n.

Execution Sample

DSA Go

func fib(n int) int {
  if n == 0 {
    return 0
  }
  dp := make([]int, n+1)
  dp[0], dp[1] = 0, 1
  for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n]
}

Calculates Fibonacci number n using a dp array to store intermediate results.

Execution Table

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

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we start filling dp array from index 2?

Because dp[0] and dp[1] are base cases set initially (see Step 2). The loop starts at i=2 to build on these known values (see Steps 3-7).

Why do we add dp[i-1] and dp[i-2] to get dp[i]?

Fibonacci number at i is sum of previous two numbers, so dp[i] = dp[i-1] + dp[i-2] (see Calculation column in Steps 3-7).

What happens if n is 0 or 1?

The function returns dp[0] or dp[1] directly from base cases without entering the loop (not shown in table but implied).

Visual Quiz - 3 Questions

Look at the execution table, what is the dp array state after Step 5?

A [0, 1, 1, 2, 3, 0, 0]

B [0, 1, 1, 2, 3, 5, 8]

C [0, 1, 1, 2, 3, 5, 0]

D [0, 1, 1, 2, 0, 0, 0]

💡 Hint

Check the 'dp Array State' column at Step 5 in the execution_table.

At which step does the dp array first contain the value 2?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Result Stored' and 'dp Array State' columns in the execution_table.

If we change the base case dp[1] from 1 to 2, what would dp[2] be after Step 3?

A 2

B 1

C 3

D 0

💡 Hint

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

Concept Snapshot

Fibonacci Using DP:
- Use an array dp to store Fibonacci numbers.
- Set dp[0] = 0 and dp[1] = 1 as base cases.
- For i from 2 to n, dp[i] = dp[i-1] + dp[i-2].
- Return dp[n] as the nth Fibonacci number.
- Avoids repeated calculations by storing results.

Full Transcript

This visualization shows how to calculate Fibonacci numbers using dynamic programming. We start by initializing a dp array with zeros and set the first two values dp[0] = 0 and dp[1] = 1 as base cases. Then, for each index i from 2 up to n, we calculate dp[i] by adding the two previous values dp[i-1] and dp[i-2]. This process fills the dp array step-by-step, storing intermediate Fibonacci numbers to avoid repeated work. Finally, we return dp[n] as the result. The execution table tracks each step, showing the dp array state and calculations. Key moments clarify why we start from index 2 and how the addition works. The quiz tests understanding of dp array states 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 randomly.

D. It uses recursion without any optimization.

Solution

1. Step 1: Understand recursion inefficiency

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

2. Step 2: Role of DP in optimization

   DP stores previously computed Fibonacci numbers in a table (memoization or tabulation), avoiding repeated work and improving efficiency.

3. Final Answer:

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

4. Quick Check:

   DP stores results = avoids repeats [OK]

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

Common Mistakes:

• Thinking DP uses less memory than recursion
• Believing DP calculates values randomly
• Confusing DP with plain recursion

2. Which of the following Go code snippets correctly initializes a slice to store Fibonacci numbers for DP with size n?

easy

A. fib := new(int)

B. fib := make([]int, n+1)

C. fib := []int{n}

D. fib := [n]int{}

Solution

1. Step 1: Understand slice initialization

   To store Fibonacci numbers up to n, we need a slice of length n+1 to hold indices 0 through n.

2. Step 2: Check each option

   fib := make([]int, n+1) uses make with length n+1, correctly creating a slice. fib := []int{n} creates a slice with one element n, not size n+1. fib := new(int) creates a pointer to int, not a slice. fib := [n]int{} is invalid syntax for slice.

3. Final Answer:

   fib := make([]int, n+1) -> Option B

4. Quick Check:

   make slice with n+1 length = correct [OK]

Hint: Use make([]int, n+1) to create DP slice for Fibonacci [OK]

Common Mistakes:

• Using array syntax instead of slice
• Creating pointer instead of slice
• Initializing slice with wrong length

3. What is the output of the following Go code snippet?

func fibDP(n int) int {
    fib := make([]int, n+1)
    fib[0], fib[1] = 0, 1
    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib[n]
}

fmt.Println(fibDP(5))

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace Fibonacci values in slice

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

2. Step 2: Return fib[5]

   The function returns fib[5], which is 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Trace fib array from 0 to n to find fib[n] [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Returning fib[n-1] instead of fib[n]
• Off-by-one errors in loop

4. Identify the error in this Go function for Fibonacci using DP and select the fix:

func fibDP(n int) int {
    fib := make([]int, n)
    fib[0], fib[1] = 0, 1
    for i := 2; i <= n; i++ {
        fib[i] = fib[i-1] + fib[i-2]
    }
    return fib[n]
}

medium

A. Return fib[n-1] instead of fib[n].

B. Initialize fib[0] and fib[1] to 1 and 1.

C. Change slice size to n+1 to avoid index out of range.

D. Change loop to for i := 1; i < n; i++.

Solution

1. Step 1: Check slice size and indexing

   Slice fib is created with length n, but loop and return access fib[n], which is out of range.

2. Step 2: Fix slice size

   Increase slice size to n+1 so fib[n] is valid and no runtime error occurs.

3. Final Answer:

   Change slice size to n+1 to avoid index out of range. -> Option C

4. Quick Check:

   Slice size must cover all indices accessed [OK]

Hint: Slice length must be at least n+1 for fib[n] access [OK]

Common Mistakes:

• Not increasing slice size causes runtime panic
• Changing initial values incorrectly
• Modifying loop incorrectly causing wrong results

5. You want to compute the 10th Fibonacci number using DP but with constant space (only two variables). Which Go code snippet correctly implements this optimization?

hard

A. func fib(n int) int {
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}

B. func fib(n int) int {
fib := make([]int, n+1)
fib[0], fib[1] = 0, 1
for i := 2; i <= n; i++ {
fib[i] = fib[i-1] + fib[i-2]
}
return fib[n]
}

C. func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}

D. func fib(n int) int {
a, b := 0, 1
for i := 1; i < n; i++ {
a = b
b = a + b
}
return a
}

Solution

1. Step 1: Understand constant space DP

   We only keep last two Fibonacci numbers and update them iteratively to save space.

2. Step 2: Analyze options

   func fib(n int) int { a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b } correctly updates a and b simultaneously and returns b as fib(n). func fib(n int) int { fib := make([]int, n+1) fib[0], fib[1] = 0, 1 for i := 2; i <= n; i++ { fib[i] = fib[i-1] + fib[i-2] } return fib[n] } uses slice (not constant space). func fib(n int) int { if n <= 1 { return n } return fib(n-1) + fib(n-2) } is simple recursion (inefficient). func fib(n int) int { a, b := 0, 1 for i := 1; i < n; i++ { a = b b = a + b } return a } updates variables incorrectly causing wrong result.

3. Final Answer:

   func fib(n int) int { a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a+b } return b } -> Option A

4. Quick Check:

   Update two vars simultaneously for constant space [OK]

Hint: Update two vars together to save space in Fibonacci DP [OK]

Common Mistakes:

• Using slice instead of variables for DP
• Incorrect variable update order causing wrong sums
• Using recursion without memoization