Fibonacci Using DP in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci DP Array

What is the printed state of the DP array after computing fibonacci(6) using bottom-up dynamic programming?

DSA C

int fibonacci(int n) {
    int dp[7] = {0};
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    for (int i = 0; i <= n; i++) {
        printf("%d ", dp[i]);
    }
    return dp[n];
}

int main() {
    fibonacci(6);
    return 0;
}

A 0 1 2 3 5 8 13

B 0 1 1 3 4 7 11

C 1 1 2 3 5 8 13

D 0 1 1 2 3 5 8

💡 Hint

Remember that fibonacci starts with 0 and 1, then each next number is sum of previous two.

The DP array starts with dp[0]=0 and dp[1]=1. Each next dp[i] is dp[i-1] + dp[i-2]. So dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8.

❓ Predict Output

intermediate

Value of fibonacci(7) with memoization

What is the value returned by fibonacci(7) using top-down memoization with dp array initialized to -1?

DSA C

int dp[8];

int fibonacci(int n) {
    if (dp[n] != -1) return dp[n];
    if (n <= 1) return n;
    dp[n] = fibonacci(n-1) + fibonacci(n-2);
    return dp[n];
}

int main() {
    for (int i = 0; i < 8; i++) dp[i] = -1;
    int result = fibonacci(7);
    printf("%d", result);
    return 0;
}

A 8

B 13

C 21

D 34

💡 Hint

Fibonacci sequence starts 0,1,1,2,3,5,8,13...

fibonacci(7) is the 7th Fibonacci number starting from 0 index: 0,1,1,2,3,5,8,13 so answer is 13.

🔧 Debug

advanced

Identify the error in DP Fibonacci code

What error will this code produce when computing fibonacci(5)?

DSA C

int fibonacci(int n) {
    int dp[5] = {0};
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    int result = fibonacci(5);
    printf("%d", result);
    return 0;
}

A Returns 5 correctly

B Compilation error: dp array size mismatch

C Runtime error: accessing dp[5] out of bounds

D Returns 0 always

💡 Hint

Check the size of dp array and the loop limits carefully.

dp array size is 5, so valid indices are 0 to 4. Accessing dp[5] causes out of bounds runtime error.

🧠 Conceptual

advanced

Time complexity of Fibonacci DP

What is the time complexity of computing fibonacci(n) using bottom-up dynamic programming with a dp array?

A O(n)

B O(2^n)

C O(n^2)

D O(log n)

💡 Hint

Each fibonacci number is computed once in bottom-up DP.

Bottom-up DP computes each fibonacci number from 0 to n once, so time complexity is linear O(n).

🚀 Application

expert

Number of calls in naive vs memoized Fibonacci

How many times is fibonacci(2) computed in naive recursive fibonacci(5) vs memoized fibonacci(5)?

A Naive: 3 times, Memoized: 1 time

B Naive: 1 time, Memoized: 1 time

C Naive: 5 times, Memoized: 2 times

D Naive: 3 times, Memoized: 3 times

💡 Hint

Memoization stores results to avoid repeated calls.

Naive recursion calls fibonacci(2) multiple times (3 times for fibonacci(5)). Memoization computes fibonacci(2) once and reuses it.