Fibonacci Using DP in DSA Python - Build from Scratch

Fibonacci Using DP

📖 Scenario: You want to find the nth number in the Fibonacci sequence quickly. The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.Using a smart way called Dynamic Programming (DP), you will save the results of smaller problems to avoid repeating work.

🎯 Goal: Build a program that calculates the nth Fibonacci number using Dynamic Programming with a list to store intermediate results.

📋 What You'll Learn

Create a list to store Fibonacci numbers up to n

Create a variable n with the value 10

Use a for loop to fill the list with Fibonacci numbers using DP

Print the nth Fibonacci number

💡 Why This Matters

🌍 Real World

Calculating Fibonacci numbers is useful in computer science for understanding sequences, algorithms, and optimization techniques.

💼 Career

Dynamic Programming is a key skill in software development and technical interviews. This project helps build a foundation for solving optimization problems efficiently.

1

Create the Fibonacci list and set n

Create a list called fib with the first two Fibonacci numbers: 0 and 1. Also create a variable called n and set it to 10.

DSA Python

# Create the fib list and set n
# Your code here

Hint

The first two Fibonacci numbers are always 0 and 1. Store them in a list called fib. Then set n to 10.

2

Prepare the list to hold all Fibonacci numbers up to n

Extend the fib list to have n + 1 elements by adding zeros. Use fib += [0] * (n - 1) to do this.

DSA Python

fib = [0, 1]
n = 10
# Extend fib list to hold n+1 elements
# Your code here

Hint

We need space in the list to store Fibonacci numbers up to index n. Add zeros to the list so its length is n + 1.

3

Fill the list with Fibonacci numbers using a for loop

Use a for loop with variable i from 2 to n inclusive. Inside the loop, set fib[i] = fib[i - 1] + fib[i - 2].

DSA Python

fib = [0, 1]
n = 10
fib += [0] * (n - 1)
# Fill fib list using DP
# Your code here

Hint

Start from index 2 because the first two Fibonacci numbers are already known. Each new number is the sum of the two before it.

4

Print the nth Fibonacci number

Print the value of fib[n].

DSA Python

fib = [0, 1]
n = 10
fib += [0] * (n - 1)
for i in range(2, n + 1):
    fib[i] = fib[i - 1] + fib[i - 2]
# Print the nth Fibonacci number
# Your code here

Hint

The 10th Fibonacci number is 55. Print fib[n] to see the result.

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