Fibonacci Using DP in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci DP with Memoization

What is the output of the following C++ code that calculates the 6th Fibonacci number using memoization?

DSA C++

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

int fib(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

int main() {
    int n = 6;
    vector<int> memo(n+1, -1);
    cout << fib(n, memo) << endl;
    return 0;
}

A 8

B 21

C 5

D 13

💡 Hint

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

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

❓ Predict Output

intermediate

Output of Bottom-Up Fibonacci DP

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

DSA C++

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

int fib(int n) {
    vector<int> dp(n+1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    cout << fib(7) << endl;
    return 0;
}

A 8

B 21

C 13

D 34

💡 Hint

Check the Fibonacci sequence values carefully for index 7.

The 7th Fibonacci number is 13 using 0-based indexing starting with 0,1,...

🔧 Debug

advanced

Identify the runtime error in Fibonacci DP code

What runtime error will this C++ code produce when calculating fib(5) using memoization?

DSA C++

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

int fib(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

int main() {
    int n = 5;
    vector<int> memo(n+1);
    cout << fib(n, memo) << endl;
    return 0;
}

A Logic error, outputs wrong Fibonacci number

B Stack overflow due to infinite recursion

C Segmentation fault due to out-of-bounds access

D No error, outputs 5

💡 Hint

Observe that the base case if (n <= 1) return n; comes before the memo check. memo[0] and memo[1] are never read.

No runtime error. The code correctly outputs 5, the 5th Fibonacci number. The base cases are handled before checking the memo, and since Fibonacci numbers for n >= 2 are positive, the != 0 check works as a sentinel for uncomputed values.

🧠 Conceptual

advanced

Time complexity of Fibonacci DP approaches

What is the time complexity of calculating the nth Fibonacci number using dynamic programming (either memoization or bottom-up)?

A O(n^2)

B O(n)

C O(2^n)

D O(log n)

💡 Hint

Dynamic programming avoids repeated calculations by storing results.

Both memoization and bottom-up DP calculate each Fibonacci number once, resulting in linear time O(n).

🚀 Application

expert

Find the number of ways to climb stairs using Fibonacci DP

You can climb 1 or 2 steps at a time. How many distinct ways are there to climb 5 steps? The code below uses Fibonacci DP logic to solve this. What is the output?

DSA C++

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

int climbStairs(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    cout << climbStairs(5) << endl;
    return 0;
}

A 8

B 5

C 10

D 13

💡 Hint

This problem maps to Fibonacci numbers shifted by one index.

Number of ways to climb 5 steps is the 6th Fibonacci number (starting dp[0]=1), which is 8.

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