Fibonacci Using DP in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the base case for Fibonacci using DP.

DSA Python

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

Drag options to blanks, or click blank then click option'

A0

B1

C2

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using fib[0] which returns 0 instead of 1.

Using fib[n] which may be out of range.

The base case for Fibonacci at index 1 is 1, so fib[1] returns 1.

2fill in blank

medium

Complete the code to fill the DP array for Fibonacci numbers.

DSA Python

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' which gives wrong sequence.

Using '*' or '//' which are incorrect operations here.

Fibonacci numbers are the sum of the two previous numbers, so use '+'.

3fill in blank

hard

Fix the error in the loop range to correctly compute Fibonacci numbers up to n.

DSA Python

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

Drag options to blanks, or click blank then click option'

A0

B1

Cn-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 0 or 1 causes overwriting base cases.

Starting at n-1 misses some Fibonacci numbers.

The loop should start at 2 because fib[0] and fib[1] are base cases.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps Fibonacci indices to their values for n numbers.

DSA Python

fib_dict = { [1]: [2] for i in range(n) }

Drag options to blanks, or click blank then click option'

Ai

Bfib[i]

Ci+1

Dfib

Attempts:

3 left

💡 Hint

Common Mistakes

Using fib as key or value which is the whole list.

Using i+1 as key which shifts indices incorrectly.

The dictionary keys are indices i, and values are fib[i].

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that includes only Fibonacci numbers greater than 5.

DSA Python

fib_filtered = { [1]: [2] for i in range(n) if [3] > 5 }

Drag options to blanks, or click blank then click option'

Ai

Bfib[i]

Di+1

Attempts:

3 left

💡 Hint

Common Mistakes

Filtering by index instead of value.

Using i+1 as key or in condition.

Keys are i, values are fib[i], and filter condition is fib[i] > 5.

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