Fibonacci Using DP in DSA Python

Mental Model

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

Analogy: Like writing down your scores in a game so you don't have to remember or redo them every time.

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

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using dynamic programming

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 previous two numbers to find the next

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

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

Why: Continue building sequence using stored values

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

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

Why: Keep adding last two known numbers

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

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

Why: Final step to get the 5th Fibonacci number

Result:

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

Annotated Code

DSA Python

class FibonacciDP:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        fib = [0] * (n + 1)
        fib[0], fib[1] = 0, 1
        for i in range(2, n + 1):
            fib[i] = fib[i - 1] + fib[i - 2]
        return fib[n]

if __name__ == '__main__':
    n = 5
    solver = FibonacciDP()
    print(solver.fib(n))

if n <= 1: return n

Handle base cases directly to avoid unnecessary computation

fib = [0] * (n + 1) fib[0], fib[1] = 0, 1

Initialize storage for Fibonacci numbers with known first two

for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2]

Build Fibonacci sequence bottom-up using stored results

return fib[n]

Return the final computed Fibonacci number

Output

5

Complexity Analysis

Time: O(n) because we compute 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 exponential O(2^n), DP is much faster by avoiding repeated work

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Python

if n <= 1:
    return n

n = 1

Returns 1 immediately as base case

DSA Python

if n <= 1:
    return n

n is large (e.g., 50)

Computes efficiently without stack overflow or repeated calculations

DSA Python

for i in range(2, n + 1):
    fib[i] = fib[i - 1] + fib[i - 2]

When to Use This Pattern

When you see a problem asking for Fibonacci or similar sequences with overlapping subproblems, use dynamic programming to store and reuse results for efficiency.

Common Mistakes

Mistake: Using naive recursion without memoization causing exponential time
Fix: Use a bottom-up DP array to store results and avoid repeated calls

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 the bottom up and save results 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 using only addition without recursion.

D. It uses randomization to speed up calculations.

Solution

1. Step 1: Understand recursive Fibonacci inefficiency

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

2. Step 2: How DP improves calculation

   DP stores previously calculated Fibonacci numbers in a table (memoization or tabulation), avoiding repeated work.

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 results to avoid repeating work [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Believing DP removes addition operations
• Confusing DP with randomization

2. Which of the following Python code snippets correctly initializes a list to store Fibonacci numbers for DP with n = 5?

easy

A. fib = [0] * 5

B. fib = [0] * 6

C. fib = [1] * 5

D. fib = []

Solution

1. Step 1: Determine list size for Fibonacci DP

   For n=5, we need indices 0 to 5 inclusive, so list size must be 6.

2. Step 2: Check initialization correctness

   fib = [0] * 6 creates a list of six zeros, ready to store fib[0] to fib[5].

3. Final Answer:

   fib = [0] * 6 -> Option B

4. Quick Check:

   List size = n+1 for fib numbers [OK]

Hint: List size must be n+1 for fib up to n [OK]

Common Mistakes:

• Using list size equal to n instead of n+1
• Initializing with ones instead of zeros
• Leaving list empty without size

3. What will be the output of the following Python code?

def fib_dp(n):
    fib = [0] * (n+1)
    fib[0], fib[1] = 0, 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

print(fib_dp(6))

medium

A. 5

B. 13

C. 8

D. 21

Solution

1. Step 1: Trace Fibonacci values up to n=6

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

2. Step 2: Return fib[6]

   The function returns fib[6], which is 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   fib(6) = 8 [OK]

Hint: Calculate fib step-by-step from base cases [OK]

Common Mistakes:

• Confusing fib(6) with fib(7)
• Starting fib from 1 instead of 0
• Off-by-one errors in loop range

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

def fib_dp(n):
    fib = [0] * n
    fib[0], fib[1] = 0, 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

medium

A. Change for loop to range(1, n)

B. Change fib[0], fib[1] = 0, 1 to fib[1], fib[2] = 0, 1

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

D. Change fib = [0] * n to fib = [0] * (n+1)

Solution

1. Step 1: Check list size for indexing

   fib list size is n, but code accesses fib[n], which is out of range.

2. Step 2: Fix list size

   Changing fib = [0] * n to fib = [0] * (n+1) allows indexing up to fib[n].

3. Final Answer:

   Change fib = [0] * n to fib = [0] * (n+1) -> Option D

4. Quick Check:

   List size must cover fib[n] index [OK]

Hint: List size must be n+1 for fib[n] access [OK]

Common Mistakes:

• Not increasing list size causes IndexError
• Changing base cases incorrectly
• Altering loop range wrongly

5. You want to find the sum of the first n Fibonacci numbers efficiently using DP. Which modification to the standard Fibonacci DP code below will correctly compute this sum?

def fib_sum(n):
    fib = [0] * (n+1)
    fib[0], fib[1] = 0, 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    # What to add here to get sum of fib[0] to fib[n]?
    return ???

hard

A. return fib[n+2] - 1

B. return fib[n] * 2

C. return fib[n] + fib[n-1]

D. return sum(fib)

Solution

1. Step 1: Understand sum of Fibonacci numbers

   The sum of first n Fibonacci numbers is fib[0] + fib[1] + ... + fib[n].

2. Step 2: Use known Fibonacci sum formula

   The sum of first n Fibonacci numbers equals fib[n+2] - 1.

3. Final Answer:

   return fib[n+2] - 1 -> Option A

4. Quick Check:

   Sum of fib numbers = fib[n+2] - 1 [OK]

Hint: Sum of first n fib numbers = fib[n+2] - 1 [OK]

Common Mistakes:

• Using fib[n]*2 which is incorrect
• Using sum(fib) which is inefficient
• Adding only last two fib numbers