Fibonacci Series using DP

Definition

The Fibonacci Sequence is a series where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8…

How it Works (The DP Way)

A normal recursive approach calculates fib(5) by calling fib(4) and fib(3). But fib(4) also calls fib(3). We end up calculating fib(3) twice!

• DP Fix: Calculate fib(3) once, save it in an array memo[3]. The next time it’s needed, just return memo[3].

Code Example (Java – Top Down)

import java.util.Arrays;

public class FibonacciDP {

    // Array to store results (memoization)
    static int[] memo = new int[100];

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        // If already solved, return stored value
        if (memo[n] != -1) {
            return memo[n];
        }

        // Otherwise calculate and store
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        // Initialize memo array with -1
        Arrays.fill(memo, -1);

        System.out.println(fib(10)); // Output: 55
    }
}

Complexity Analysis

• Time Complexity: O(N). We calculate each number from 0 to N exactly once. (Naive recursion is O(2^N) terrible)
• Space Complexity: O(N) for the array and recursion stack.