Fibonacci Using DP in DSA C++

Mental Model

We remember past Fibonacci numbers so we don't repeat work. This saves time by building answers step-by-step.

Analogy: Like climbing stairs and writing down how many ways to reach each step so you don't count again.

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

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using DP

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: We use stored values to find next Fibonacci number

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

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

Why: Build next number using previous two

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

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

Why: Continue building sequence step-by-step

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

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

Why: Final Fibonacci number for n=5 found using stored results

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Function to calculate nth Fibonacci number using DP
int fibonacciDP(int n) {
    if (n <= 1) return n; // base cases
    vector<int> fib(n + 1, 0); // create array to store Fibonacci numbers
    fib[0] = 0; // fib(0)
    fib[1] = 1; // fib(1)
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // build fib[i] from previous two
    }
    return fib[n]; // return nth Fibonacci number
}

int main() {
    int n = 5;
    cout << fibonacciDP(n) << endl;
    return 0;
}

if (n <= 1) return n; // base cases

return known Fibonacci values for 0 and 1 immediately

vector<int> fib(n + 1, 0); // create array to store Fibonacci numbers

prepare storage to remember all Fibonacci numbers up to n

fib[0] = 0; // fib(0)

initialize base Fibonacci number 0

fib[1] = 1; // fib(1)

initialize base Fibonacci number 1

for (int i = 2; i <= n; i++) {

loop from 2 to n to fill Fibonacci numbers step-by-step

fib[i] = fib[i - 1] + fib[i - 2]; // build fib[i] from previous two

calculate current Fibonacci number using last two stored values

return fib[n]; // return nth Fibonacci number

return the final answer after building all values

Output

5

Complexity Analysis

Time: O(n) because we compute each Fibonacci number from 2 to n once

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 calculations

Edge Cases

n = 0

Returns 0 immediately as base case

DSA C++

if (n <= 1) return n; // base cases

n = 1

Returns 1 immediately as base case

DSA C++

if (n <= 1) return n; // base cases

large n (e.g., 50)

Calculates efficiently without repeated work, but may need larger integer type for big values

DSA C++

vector<int> fib(n + 1, 0); // create array to store Fibonacci numbers

When to Use This Pattern

When you see a problem asking for Fibonacci or similar sequences, use DP to store intermediate results and avoid repeated work.

Common Mistakes

Mistake: Using naive recursion without memoization causing exponential time
Fix: Use an array to store computed Fibonacci numbers and build up from base cases

Mistake: Not initializing base cases fib[0] and fib[1]
Fix: Always set fib[0] = 0 and fib[1] = 1 before the loop

Summary

Calculates Fibonacci numbers efficiently by storing previous results.

Use when you want to avoid repeated calculations in Fibonacci or similar sequences.

Remember to build answers step-by-step using stored smaller results.

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 uses less memory by not storing any results.

B. It avoids repeated calculations by storing intermediate results.

C. It calculates Fibonacci numbers using only addition.

D. It uses a recursive function without any loops.

Solution

1. Step 1: Understand recursion vs DP

   Simple recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

2. Step 2: Role of DP in Fibonacci

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

3. Final Answer:

   It avoids repeated calculations by storing intermediate results. -> Option B

4. Quick Check:

   DP = store results to avoid repeats [OK]

Hint: DP saves results to skip repeated work [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Confusing DP with simple recursion
• Believing DP avoids addition operations

2. Which of the following C++ code snippets correctly initializes the base cases for Fibonacci using bottom-up DP?

easy

A. int fib[10]; fib[0] = 0; fib[1] = 1;

B. int fib[10]; fib[1] = 0; fib[2] = 1;

C. int fib[10]; fib[0] = 1; fib[1] = 1;

D. int fib[10]; fib[0] = 1; fib[2] = 0;

Solution

1. Step 1: Identify Fibonacci base cases

   Fibonacci sequence starts with fib(0) = 0 and fib(1) = 1.

2. Step 2: Check initialization correctness

   int fib[10]; fib[0] = 0; fib[1] = 1; correctly sets fib[0] = 0 and fib[1] = 1, matching the base cases.

3. Final Answer:

   int fib[10]; fib[0] = 0; fib[1] = 1; -> Option A

4. Quick Check:

   fib[0]=0, fib[1]=1 base cases [OK]

Hint: Base cases: fib[0]=0 and fib[1]=1 [OK]

Common Mistakes:

• Starting fib from index 1 instead of 0
• Swapping values of fib[0] and fib[1]
• Initializing wrong indices

3. What is the output of the following C++ code snippet?

int fib[6];
fib[0] = 0; fib[1] = 1;
for(int i = 2; i < 6; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
std::cout << fib[5];

medium

A. 5

B. 8

C. 13

D. 21

Solution

1. Step 1: Calculate Fibonacci values step-by-step

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

2. Step 2: Identify output

   The code prints fib[5], which is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib[5]=5 [OK]

Hint: Calculate fib stepwise from base cases [OK]

Common Mistakes:

• Confusing fib[5] with fib[6]
• Off-by-one errors in loop
• Incorrect addition order

4. Identify the error in the following Fibonacci DP code and choose the correct fix:

int fib[10];
fib[0] = 0;
fib[1] = 1;
for(int i = 1; i < 10; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
std::cout << fib[9];

medium

A. Change loop condition to i <= 10

B. Initialize fib[2] before the loop

C. Change fib[0] to 1

D. Change loop start to i = 2

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but fib[1] is already initialized. Calculating fib[1] again causes fib[-1] access (invalid).

2. Step 2: Correct loop start

   Loop should start at i=2 to use fib[i-1] and fib[i-2] safely.

3. Final Answer:

   Change loop start to i = 2 -> Option D

4. Quick Check:

   Loop from i=2 avoids invalid index [OK]

Hint: Start loop at 2 to avoid negative index [OK]

Common Mistakes:

• Starting loop at 1 causing invalid access
• Changing base case values incorrectly
• Extending loop beyond array size

5. You want to find the 50th Fibonacci number using DP in C++. Which approach is best to handle large Fibonacci numbers efficiently and why?

hard

A. Use bottom-up DP with int array since int can hold large numbers.

B. Use simple recursion without memoization for clarity.

C. Use a vector of unsigned long long and bottom-up DP to avoid recursion overhead.

D. Use recursion with memoization but store results in int array.

Solution

1. Step 1: Consider data type size

   50th Fibonacci number is very large; int cannot hold it, unsigned long long can hold bigger values.

2. Step 2: Choose DP approach

   Bottom-up DP avoids recursion overhead and stack issues, making it efficient for large n.

3. Final Answer:

   Use a vector of unsigned long long and bottom-up DP to avoid recursion overhead. -> Option C

4. Quick Check:

   Big number + bottom-up DP = efficient and safe [OK]

Hint: Use big data type and bottom-up DP for large n [OK]

Common Mistakes:

• Using int causing overflow
• Using recursion causing stack overflow
• Ignoring data type limits