Fibonacci Using DP in DSA Go

Mental Model

Remember past Fibonacci numbers so you don't calculate them again.

Analogy: Like writing down each step of a recipe so you don't have to guess or redo steps later.

fib[0] = 0
fib[1] = 1
fib[2] = ?
fib[3] = ?
fib[4] = ?
...

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using DP

Goal: Find the 5th Fibonacci number efficiently by storing previous results

Step 1: Initialize fib array with fib[0]=0 and fib[1]=1

fib: [0, 1, ?, ?, ?, ?]

Why: Base cases are known and needed to build next numbers

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0

fib: [0, 1, 1, ?, ?, ?]

Why: Use stored values to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1

fib: [0, 1, 1, 2, ?, ?]

Why: Build next number from previous two

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1

fib: [0, 1, 1, 2, 3, ?]

Why: Continue building sequence using stored results

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2

fib: [0, 1, 1, 2, 3, 5]

Why: Final Fibonacci number for n=5 found efficiently

Result:

fib: [0, 1, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA Go

package main

import "fmt"

func fibonacciDP(n int) int {
	if n <= 1 {
		return n
	}
	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]
}

func main() {
	result := fibonacciDP(5)
	fmt.Println(result)
}

if n <= 1 { return n }

Handle base cases directly to avoid unnecessary computation

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

Initialize array to store Fibonacci numbers with base values

for i := 2; i <= n; i++ { fib[i] = fib[i-1] + fib[i-2] }

Fill array by summing previous two Fibonacci numbers

return fib[n]

Return the nth Fibonacci number from stored results

Output

5

Complexity Analysis

Time: O(n) because we calculate each Fibonacci number once from 2 to n

Space: O(n) because we store all Fibonacci numbers up to n in an array

vs Alternative: Compared to naive recursion which is O(2^n), DP is much faster by avoiding repeated calculations

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Go

if n <= 1 {
	return n
}

n = 1

Returns 1 immediately as base case

DSA Go

if n <= 1 {
	return n
}

n is large (e.g., 50)

Calculates efficiently without stack overflow or repeated work

DSA Go

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

When to Use This Pattern

When you see a problem asking for Fibonacci or similar sequences, use DP to store past results and avoid repeated work.

Common Mistakes

Mistake: Using naive recursion without memoization causing exponential time
Fix: Use an array to store results and build up from base cases

Mistake: Not handling base cases n=0 or n=1 correctly
Fix: Add explicit checks to return n when n <= 1

Summary

Calculates Fibonacci numbers efficiently by storing previous results.

Use when you need Fibonacci numbers or similar sequences without repeated calculations.

Remember to build from base cases and store each result to avoid repeated work.

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