Fibonacci Using DP in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using Dynamic Programming (DP) to calculate Fibonacci numbers?

DP stores the results of smaller subproblems (previous Fibonacci numbers) to avoid repeated calculations, making the process faster and efficient.

beginner

In Fibonacci using DP, what does the 'memoization' technique mean?

Memoization means saving the results of Fibonacci calculations in a table (array or map) so that when the same number is needed again, it can be returned immediately without recalculating.

intermediate

Why is the time complexity of Fibonacci using DP O(n) instead of exponential?

Because each Fibonacci number from 0 to n is calculated once and stored, so the function does not repeat calculations, reducing time from exponential to linear.

intermediate

What is the difference between top-down and bottom-up approaches in Fibonacci DP?

Top-down uses recursion with memoization (solves big problem by breaking down), while bottom-up builds the solution iteratively from the smallest subproblems up to the desired number.

beginner

Show the base cases used in Fibonacci DP and explain why they are important.

Base cases are Fib(0) = 0 and Fib(1) = 1. They stop the recursion or start the iteration and provide known values to build the rest of the sequence.

What does DP store to avoid repeated Fibonacci calculations?

A Previous Fibonacci numbers

B Random numbers

C Only the last Fibonacci number

D No values are stored

DP stores previous Fibonacci numbers to reuse them and avoid recalculating.

Which approach uses recursion with memoization in Fibonacci DP?

A Bottom-up

B Top-down

C Iterative

D Greedy

Top-down approach uses recursion with memoization.

What is the time complexity of Fibonacci using DP?

A O(2^n)

B O(n^2)

C O(log n)

D O(n)

DP calculates each Fibonacci number once, so time complexity is O(n).

What are the base cases for Fibonacci DP?

A Fib(0)=0, Fib(1)=1

B Fib(0)=1, Fib(1)=1

C Fib(0)=1, Fib(1)=0

D Fib(0)=0, Fib(1)=0

Base cases are Fib(0)=0 and Fib(1)=1.

Which of these is NOT a benefit of using DP for Fibonacci?

A Avoids repeated calculations

B Uses extra memory to store results

C Increases time complexity exponentially

D Improves efficiency

DP reduces time complexity; it does not increase it exponentially.

Explain how memoization helps in calculating Fibonacci numbers efficiently.

Think about saving answers to smaller problems.

Describe the difference between top-down and bottom-up approaches in Fibonacci DP.

One starts from the big problem, the other from the small.

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