Why Fibonacci Using DP in DSA Go?

The Big Idea

What if you could save every answer you find and never do the same hard work twice?

The Scenario

Imagine you want to find the 40th number in the Fibonacci sequence by calculating each number one by one, starting from the beginning.

You write a simple function that calls itself to find the previous two numbers, then adds them together.

The Problem

This manual method repeats the same calculations many times, making it very slow and frustrating.

For example, to find the 40th number, it recalculates the 39th and 38th numbers, and each of those recalculates their previous numbers again and again.

This wastes time and computer power.

The Solution

Dynamic Programming (DP) solves this by remembering the answers it already found.

Instead of recalculating, it stores results in a list and uses them when needed.

This makes finding the 40th number much faster and easier.

Before vs After

✗ Before

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

✓ After

func fib(n int) int {
    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]
}

What It Enables

DP lets us solve big problems quickly by building on smaller answers we already know.

Real Life Example

Calculating the number of ways to climb stairs when you can take one or two steps at a time is like Fibonacci and can be solved efficiently with DP.

Key Takeaways

Manual Fibonacci repeats work and is slow.

DP stores results to avoid repeated work.

DP makes solving big problems fast and simple.

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