Fibonacci Using DP in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of this code that calculates the 6th Fibonacci number using memoization (top-down dynamic programming)?

DSA Python

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(6))

A 5

B 13

C 8

D 21

💡 Hint

Remember Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8...

The 6th Fibonacci number (0-based index) is 8. The function uses memoization to avoid repeated calculations.

❓ Predict Output

intermediate

Output of Fibonacci with Tabulation

What is the output of this code that calculates the 7th Fibonacci number using tabulation (bottom-up dynamic programming)?

DSA Python

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_tab(7))

A 34

B 13

C 21

D 8

💡 Hint

Count carefully starting from 0: 0,1,1,2,3,5,8,13...

The 7th Fibonacci number (0-based) is 13. The code builds the sequence from the bottom up.

🔧 Debug

advanced

Identify the error in Fibonacci memoization code

What error does this code raise when trying to compute fib_memo(5)?

DSA Python

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(5))

A No error, output is 5

B TypeError: unhashable type: 'dict'

C RecursionError: maximum recursion depth exceeded

D KeyError: 5

💡 Hint

Check the order of base case and memo check.

The code runs correctly and outputs 5. The base case is checked before memo lookup, so no infinite recursion occurs.

❓ Predict Output

advanced

Output of Fibonacci with space optimization

What is the output of this code that calculates the 8th Fibonacci number using space optimized bottom-up approach?

DSA Python

def fib_optimized(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

print(fib_optimized(8))

A 34

B 21

C 55

D 13

💡 Hint

Remember the sequence: 0,1,1,2,3,5,8,13,21,34...

The 8th Fibonacci number (0-based) is 21. The code uses two variables to save space.

🧠 Conceptual

expert

Why use dynamic programming for Fibonacci?

Which of the following best explains why dynamic programming is used to calculate Fibonacci numbers efficiently?

A It uses randomization to guess Fibonacci numbers quickly.

B It uses recursion without storing results, which makes the code simpler and faster.

C It calculates Fibonacci numbers using matrix multiplication for constant time complexity.

D It avoids repeated calculations by storing results of subproblems, reducing time complexity from exponential to linear.

💡 Hint

Think about how repeated work is avoided.

Dynamic programming stores results of smaller problems to avoid recalculating them, making Fibonacci calculation efficient.

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