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.