Fibonacci with Dynamic Programming Explained — Memoization vs Tabulation

public class NaiveFibonacci {

    /**
     * Naive recursive Fibonacci — correct but catastrophically slow.
     * Time complexity: O(2^n)  — doubles the work for every extra step.
     * Space complexity: O(n)   — call stack depth equals n.
     */
    public static long fib(int n) {
        // Base cases: fib(0) = 0, fib(1) = 1 — the sequence's starting seeds
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Every call spawns TWO more calls — this is where the explosion happens
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        // These small values are fine — the tree is tiny
        System.out.println("fib(5)  = " + fib(5));
        System.out.println("fib(10) = " + fib(10));
        System.out.println("fib(20) = " + fib(20));

        // Count how many times fib(3) is recalculated inside fib(10)
        // (It's called 8 times — wasteful even at n=10)
        System.out.println("\nfib(40) = " + fib(40)); // starts to feel slow
        // DO NOT try fib(60) here — it will run for minutes
        System.out.println("\nNotice fib(40) was slow. Imagine fib(80).");
    }
}

import java.util.Arrays;

public class MemoizedFibonacci {

    /**
     * Top-Down Dynamic Programming — Memoization.
     * We use a memo array as our 'notebook'.
     * Time:  O(n) — each unique fib value computed exactly once.
     * Space: O(n) — memo array + recursive call stack.
     */
    public static long fib(int n, long[] memo) {
        // Base cases — the two seeds every Fibonacci sequence starts from
        if (n == 0) return 0;
        if (n == 1) return 1;

        // CHECK THE NOTEBOOK FIRST — did we already compute this?
        // memo[n] != -1 means we've been here before and stored the answer
        if (memo[n] != -1) {
            return memo[n]; // Return instantly — zero recursion needed
        }

        // First time visiting fib(n) — compute it the normal recursive way...
        long result = fib(n - 1, memo) + fib(n - 2, memo);

        // ...then WRITE IT IN THE NOTEBOOK before returning
        memo[n] = result;

        return result;
    }

    public static void main(String[] args) {
        int target = 50;

        // Create the memo array, sized (target + 1) so index n maps to fib(n)
        // Fill with -1 to mean 'not yet computed'
        long[] memo = new long[target + 1];
        Arrays.fill(memo, -1);

        System.out.println("=== Memoized Fibonacci ===");

        // These will all be instant — even fib(50) completes in microseconds
        for (int i = 0; i <= 10; i++) {
            // Reuse the same memo table — values computed earlier help later calls
            System.out.printf("fib(%2d) = %d%n", i, fib(i, memo));
        }

        System.out.println("...");
        System.out.printf("fib(50) = %d%n", fib(target, memo));
        System.out.println("\nCompleted instantly. Compare that to naive recursion.");
    }
}

public class TabulatedFibonacci {

    /**
     * Bottom-Up Dynamic Programming — Tabulation.
     * Build the answer from the ground up using a table.
     * Time:  O(n) — single pass through the loop.
     * Space: O(n) — the fibTable array stores all intermediate results.
     */
    public static long fibTableFull(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        // Create a table where index i will hold the value of fib(i)
        long[] fibTable = new long[n + 1];

        // Seed the table with the two values we know for certain
        fibTable[0] = 0; // fib(0) is defined as 0
        fibTable[1] = 1; // fib(1) is defined as 1

        // Fill every cell from index 2 upward — each depends only on earlier cells
        for (int position = 2; position <= n; position++) {
            // The core DP recurrence: sum the two cells immediately before this one
            fibTable[position] = fibTable[position - 1] + fibTable[position - 2];
        }

        // The answer we want is sitting at the end of the table
        return fibTable[n];
    }

    /**
     * Space-Optimised Tabulation — O(1) space.
     * We only ever need the PREVIOUS TWO values, so we ditch the full table.
     * This is the version you want in memory-constrained environments.
     * Time:  O(n) — same single loop.
     * Space: O(1) — just three variables, no array.
     */
    public static long fibSpaceOptimised(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        long previousPrevious = 0; // Represents fib(i-2)
        long previous         = 1; // Represents fib(i-1)
        long current          = 0; // Will hold fib(i) each iteration

        for (int step = 2; step <= n; step++) {
            current = previous + previousPrevious; // Compute this step's fib value
            previousPrevious = previous;           // Slide the window forward
            previous = current;                    // Slide the window forward
        }

        return current;
    }

    public static void main(String[] args) {
        System.out.println("=== Tabulated Fibonacci (Full Table) ===");
        for (int i = 0; i <= 10; i++) {
            System.out.printf("fib(%2d) = %d%n", i, fibTableFull(i));
        }
        System.out.printf("fib(50) = %d%n%n", fibTableFull(50));

        System.out.println("=== Space-Optimised Fibonacci (O(1) space) ===");
        System.out.printf("fib(50) = %d%n",  fibSpaceOptimised(50));
        System.out.printf("fib(70) = %d%n",  fibSpaceOptimised(70));
        System.out.println("\nSame answers, no array needed — just three variables.");
    }
}