The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Examples

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints

  • 0 <= n <= 30

Thinking Process

  1. Bottom-Up DP: Build solution from base cases upward
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

Time Complexity: O(n) - Single pass through the array
Space Complexity: O(n) - Cache array (can be optimized to O(1))

This solution uses bottom-up dynamic programming with memoization to avoid recalculating Fibonacci numbers.

Solution: DP with Cache Array

class Solution {
        public int fib(int n) {
        int[] cache = new int[n + 1];

        if(n <) return 0;
        if(n == 1) return 1;

        cache[0] = 0;
        cache[1] = 1;

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

        return cache[n];
    }
}

Solution Explanation

Approach: 1D DP (this problem)

Key idea: 1. Bottom-Up DP: Build solution from base cases upward

How the code works:

  1. Bottom-Up DP: Build solution from base cases upward
    • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
    • Recurrence: how does the answer build from smaller indices?
    • Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input n = 2, expected output 1:

F(2) = F(1) + F(0) = 1 + 0 = 1.

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | DP with Cache | O(n) | O(n) | Simple, clear | O(n) space | | Space-Optimized | O(n) | O(1) | Optimal space | Can’t access history | | Recursive + Memo | O(n) | O(n) | Intuitive | Stack overhead | | Pure Recursion | O(2^n) | O(n) | Simple | Extremely slow | | Matrix Exponentiation | O(log n) | O(1) | Very fast | Complex |

Algorithm Breakdown

class Solution {
        public int fib(int n) {
        if(n <) return 0;
        if(n == 1) return 1;
        prev2 = 0; // F(0)
        prev1 = 1; // F(1)

        for(int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
}

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | DP with Cache | O(n) | O(n) | Simple, clear | O(n) space | | Space-Optimized | O(n) | O(1) | Optimal space | Can’t access history | | Recursive + Memo | O(n) | O(n) | Intuitive | Stack overhead | | Pure Recursion | O(2^n) | O(n) | Simple | Extremely slow | | Matrix Exponentiation | O(log n) | O(1) | Very fast | Complex |

Implementation Details

Cache Initialization

class Solution {
        public int fib(int n) {
        public int[] memo(n + 1, -1);
        return fibHelper = new return(n, memo);
    }
        public int fibHelper(int n, int[] memo) {
        if(n <) return 0;
        if(n == 1) return 1;

        if(memo[n] != -1) return memo[n];

        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }
}

Creates an array of size n + 1 initialized to 0. This allows indexing from 0 to n.

Base Case Handling

class Solution {
        public int fib(int n) {
        if(n <) return 0;
        if(n == 1) return 1;
        return fib(n - 1) + fib(n - 2);
    }
}

Early returns for base cases avoid unnecessary computation and array access.

Loop Construction

class Solution {
        public int fib(int n) {
        if(n <) return 0;
        if(n == 1) return 1;

        // Matrix: [F(n+1) F(n)  ] = [1 1]^n
        //         [F(n)   F(n-1)]   [1 0]
        int[][] base = new int[][] {new int[] {1, 1}, new int[] {1, 0}};
        int[][] result = matrixPower(base, n);

        return result[0][1];
    }
    int[][] matrixPower(int[][] m, int n) {
        if(n == 1) return m;

        int[][] half = matrixPower(m, n / 2);
        int[][] result = matrixMultiply(half, half);

        if(n % 2 == 1) {
            result = matrixMultiply(result, m);
        }

        return result;
    }

    int[][] matrixMultiply(int[][] a, int[][] b) {
        return {
            {a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]},
            {a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]}
        }
    }
}

Builds Fibonacci numbers sequentially from F(2) to F(n).

Common Mistakes

  1. n = 0: Return 0
  2. n = 1: Return 1
  3. n = 2: Return 1 (first non-base Fibonacci number)

  4. n = 30: Maximum constraint value

  5. Off-by-one errors: Using i < n instead of i <= n
  6. Array bounds: Not allocating n + 1 elements
  7. Base case order: Checking n == 1 before n <= 0
  8. Uninitialized cache: Not setting cache[0] and cache[1]
  9. Wrong return value: Returning cache[n-1] instead of cache[n]

Optimization Tips

  1. Space Optimization: Use two variables instead of array for O(1) space
  2. Early Returns: Handle base cases immediately
  3. Memoization: Cache results to avoid recalculation (already done in DP)
  4. Matrix Exponentiation: Use for very large n (though n ≤ 30 here)

Real-World Applications

  1. Algorithm Analysis: Fibonacci heap data structure
  2. Nature: Modeling growth patterns (pinecones, sunflowers)
  3. Art: Golden ratio and aesthetic proportions
  4. Computer Science: Dynamic programming examples
  5. Mathematics: Number theory and sequences

Pattern Recognition

This problem demonstrates the “Classic DP Pattern”:

1. Identify base cases
2. Define recurrence relation
3. Build solution bottom-up or top-down
4. Optimize space if possible

Similar problems:

  • Climbing Stairs
  • Min Cost Climbing Stairs
  • Tribonacci Number
  • House Robber (with constraints)

Fibonacci Sequence Properties

  1. Golden Ratio: As n increases, F(n+1)/F(n) approaches φ ≈ 1.618
  2. Binet’s Formula: Closed-form solution using golden ratio
  3. Pisano Period: Fibonacci modulo m has a repeating cycle
  4. Sum Property: Sum of first n Fibonacci numbers = F(n+2) - 1

Why DP is Preferred

  1. Avoids Recalculation: Pure recursion recalculates F(3) multiple times
  2. Efficient: O(n) time vs O(2^n) for naive recursion
  3. Simple: Easy to understand and implement
  4. Space Trade-off: Can optimize to O(1) space easily

This problem is a perfect introduction to dynamic programming, demonstrating how memoization can transform exponential time complexity into linear time.

Key Takeaways

  1. Bottom-Up DP: Build solution from base cases upward
  2. Memoization: Store previously computed values to avoid recalculation
  3. Base Cases: F(0) = 0 and F(1) = 1 are the foundation
  4. Recurrence Relation: F(n) = F(n-1) + F(n-2) for n > 1
  5. Overlapping Subproblems: Each Fibonacci number depends on previous two

References

Template Reference