Tabulation Bottom Up DP in DSA C

Mental Model

Build the answer step-by-step from the smallest parts up, storing results in a table to avoid repeating work.

Analogy: Like filling a staircase from the bottom step to the top, each step depends on the ones below it, so you solve small steps first and use them to reach the top.

Table: [0] [1] [2] [3] [4] ...
Values:  0   ?   ?   ?   ?  ...
↑ start filling from left to right

Dry Run Walkthrough

Input: Find the 5th Fibonacci number using bottom-up DP

Goal: Calculate Fibonacci(5) by filling a table from the base cases up to 5

Step 1: Initialize base cases: fib[0] = 0, fib[1] = 1

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

Why: We need starting points to build the rest

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

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

Why: Use known values to find next

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

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

Why: Build on previous results

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

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

Why: Continue building up

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

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

Why: Final answer reached

Result:

fib: 0 -> 1 -> 1 -> 2 -> 3 -> 5
Answer: 5

Annotated Code

DSA C

#include <stdio.h>

// Function to find nth Fibonacci number using bottom-up DP
int fibonacci(int n) {
    if (n == 0) return 0;
    int fib[n+1];
    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 from smaller subproblems
    }
    return fib[n];
}

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

fib[0] = 0; // base case

Set first known Fibonacci number

fib[1] = 1; // base case

Set second known Fibonacci number

for (int i = 2; i <= n; i++) { fib[i] = fib[i-1] + fib[i-2]; }

Fill table from bottom up using previous two values

return fib[n];

Return final computed Fibonacci number

Output

Fibonacci(5) = 5

Complexity Analysis

Time: O(n) because we fill the table once from 0 to n

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

vs Alternative: Compared to naive recursion which is exponential, tabulation is much faster and avoids repeated work

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

fib[1] = 1; // base case

When to Use This Pattern

When you see a problem where the answer depends on smaller subproblems and you want to avoid repeated calculations, use bottom-up tabulation to build the solution step-by-step.

Common Mistakes

Mistake: Starting the loop from 0 or 1 instead of 2 causes incorrect overwriting of base cases
Fix: Start the loop from 2 because base cases at 0 and 1 are already set

Mistake: Not allocating enough space for the array causes out-of-bounds errors
Fix: Declare array size as n+1 to include index n

Summary

Calculates answers by filling a table from smallest to largest subproblems.

Use when a problem can be broken into smaller overlapping subproblems.

Build solutions bottom-up to avoid repeated work and save time.