Fibonacci (Tabulation)

Dynamic Programming O(n) O(n)

Builds the Fibonacci sequence bottom-up, each term being the sum of the two before it — no repeated work.

i	0	1	2	3	4	5	6	7	8
fib	0	·	·	·	·	·	·	·	·

1/10

Base case: dp[0] = 0.

Invariantdp[i] is final once written; each subproblem is solved exactly once, which is what removes the exponential blow-up.

computingreads fromfilled

fibonacci.c

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

How Fibonacci (Tabulation) works

Build the sequence bottom-up in a table: each entry is the sum of the previous two. Tabulation turns the exponential recursion tree into a single linear sweep.

When to use it

The 'hello world' of DP — the pattern (memoize overlapping subproblems) is what transfers.