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 remembering how many ways to reach each step so you don't count again.

Fib array: [0, 1, _, _, _, ...]
Index:     0  1  2  3  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 base cases fib[0]=0 and fib[1]=1

fib: [0, 1, _, _, _, _]

Why: We need starting points to build next Fibonacci numbers

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

fib: [0, 1, 1, _, _, _]

Why: Each Fibonacci number is sum of two before it

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

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

Why: Build next number using stored results

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

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

Why: Continue building up to target

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

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

Why: Final Fibonacci number for n=5 found

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Function to calculate Fibonacci using DP
int fibonacci_dp(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int *fib = (int *)malloc((n + 1) * sizeof(int));
    fib[0] = 0; // base case
    fib[1] = 1; // base case

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // build current from previous two
    }

    int result = fib[n];
    free(fib);
    return result;
}

int main() {
    int n = 5;
    int result = fibonacci_dp(n);
    printf("Fibonacci number for n=%d is %d\n", n, result);
    return 0;
}

fib[0] = 0; // base case

initialize first Fibonacci number

fib[1] = 1; // base case

initialize second Fibonacci number

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

loop from 2 to n to fill Fibonacci array

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

calculate current Fibonacci number using previous two

int result = fib[n];

store final Fibonacci number to return

free(fib);

release allocated memory

Output

Fibonacci number for n=5 is 5

Complexity Analysis

Time: O(n) because we calculate each Fibonacci number once from the two before it

Space: O(n) because we store all Fibonacci numbers up to n in an array

vs Alternative: Compared to naive recursion which is 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 == 0) return 0;

n = 1

Returns 1 immediately as base case

DSA C

if (n == 1) return 1;

large n (e.g., 50)

Calculates efficiently without stack overflow unlike recursion

DSA C

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

When to Use This Pattern

When you see repeated calculations of Fibonacci or similar sequences, use DP to store intermediate results and avoid recomputation.

Common Mistakes

Mistake: Using recursion without memoization causing exponential time
Fix: Use DP array to store results and build up iteratively

Mistake: Not handling base cases n=0 or n=1 correctly
Fix: Add explicit checks for n=0 and n=1 before loop

Summary

Calculates Fibonacci numbers efficiently by storing previous results.

Use when you want fast Fibonacci calculation without repeated work.

Remember: build answers step-by-step using stored smaller answers.

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 stores intermediate results to avoid repeated calculations

B. It uses more memory without improving speed

C. It calculates Fibonacci numbers randomly

D. It only works for small Fibonacci numbers

Solution

1. Step 1: Understand recursion vs DP

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

2. Step 2: Role of DP in Fibonacci

   DP saves previously calculated Fibonacci values in a table (memoization or tabulation), avoiding repeated work.

3. Final Answer:

   It stores intermediate results to avoid repeated calculations -> Option A

4. Quick Check:

   DP = stores results to save time [OK]

Hint: DP saves past answers to speed up Fibonacci [OK]

Common Mistakes:

• Thinking DP uses more memory without speed benefit
• Believing DP calculates numbers randomly
• Assuming DP only works for small inputs

2. Which of the following is the correct way to initialize the base cases in a bottom-up DP approach for Fibonacci in C?

easy

A. int fib[2] = {0, 0};

B. int fib[2] = {1, 1};

C. int fib[2] = {0, 1};

D. int fib[2] = {1, 0};

Solution

1. Step 1: Identify Fibonacci base cases

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

2. Step 2: Match initialization with base cases

   Array fib[2] = {0, 1} correctly sets fib(0) = 0 and fib(1) = 1.

3. Final Answer:

   int fib[2] = {0, 1}; -> Option C

4. Quick Check:

   Base fib = 0,1 [OK]

Hint: Start fib with 0 and 1 for base cases [OK]

Common Mistakes:

• Swapping the order of 0 and 1
• Setting both base cases to 1
• Initializing both to zero

3. What is the output of the following C code snippet using bottom-up DP to find fib(5)?

int fib[6];
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i <= 5; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
printf("%d", fib[5]);

medium

A. 5

B. 8

C. 3

D. 13

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 fib[5]

   fib[5] is 5 after the loop completes.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Calculate fib stepwise from 0 and 1 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Starting loop from wrong index
• Off-by-one errors in array indexing

4. Identify the error in this DP Fibonacci code snippet and select 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];
}

medium

A. Initialize fib[2] before loop

B. Change loop to start from i = 2

C. Change loop condition to i <= 10

D. No error, code is correct

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but fib[1] is already initialized, so fib[1] gets overwritten incorrectly.

2. Step 2: Correct loop start

   Loop should start at i=2 to use fib[0] and fib[1] for calculation without overwriting base cases.

3. Final Answer:

   Change loop to start from i = 2 -> Option B

4. Quick Check:

   Loop start = 2 fixes overwrite [OK]

Hint: Start loop after base cases to avoid overwrite [OK]

Common Mistakes:

• Starting loop at 1 overwrites fib[1]
• Not initializing base cases properly
• Using wrong loop end condition

5. You want to find the 10th Fibonacci number using DP but with optimized space using only two variables instead of an array. Which code snippet correctly implements this?

hard

A. int a = 0, b = 1, c, n = 10;
for(int i = 0; i < n; i++) {
c = a + b;
a = c;
b = a;
}
printf("%d", c);

B. int a = 0, b = 1, c, n = 10;
for(int i = 1; i < n; i++) {
c = a + b;
b = a;
a = c;
}
printf("%d", a);

C. int a = 1, b = 1, c, n = 10;
for(int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
printf("%d", c);

D. int a = 0, b = 1, c, n = 10;
for(int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
printf("%d", b);

Solution

1. Step 1: Understand space optimization

   Only two variables (a, b) track last two Fibonacci numbers; c stores current sum.

2. Step 2: Check loop and updates

   Loop from 2 to n, update c = a + b, then shift a = b, b = c correctly to move forward.

3. Final Answer:

   Code snippet A correctly implements optimized Fibonacci calculation -> Option D

4. Quick Check:

   Two vars + sum update = correct [OK]

Hint: Use two vars and update in loop for space optimization [OK]

Common Mistakes:

• Swapping updates of a and b incorrectly
• Wrong loop range causing off-by-one errors
• Initializing variables incorrectly