Skip to main content

🌟 Fibonacci Number - The Discovery Journey

The Problem (Quick Glance)​

LC 509: Fibonacci Number

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.

Given n, calculate F(n).

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

Initial Observations:

  • This is the foundation pattern for Pattern 1a: Simple Accumulation
  • Classic recursive definition: F(n) = F(n-1) + F(n-2)
  • Base cases: F(0) = 0, F(1) = 1
  • Pure accumulation - no constraints or conditions

1. My First Approach: Thinking Recursively​

COMING SOON

This section will explore:

  • Pure recursive solution
  • Why it's exponentially slow (O(2^n))
  • The recursive tree structure
  • Identifying repeated subproblems

2. Optimization Round 1: Adding Memoization​

COMING SOON

This section will cover:

  • Top-down DP with memoization
  • How caching eliminates redundant work
  • Complexity improvement: O(2^n) → O(n)
  • Understanding the memo array

3. Optimization Round 2: Going Iterative​

COMING SOON

This section will demonstrate:

  • Bottom-up DP with tabulation
  • Building solution iteratively
  • No recursion stack overhead
  • Cleaner and more efficient approach

4. Final Optimization: Space Optimization​

COMING SOON

This section will show:

  • Reducing space to O(1)
  • Only tracking last 2 values
  • The sliding window technique
  • Why Fibonacci is perfect for space optimization

5. Solution Evolution Summary​

COMING SOON
ApproachTimeSpaceKey Insight
1. Pure RecursiveO(2^n)O(n)Natural problem definition
2. MemoizationO(n)O(n)Cache to avoid recomputation
3. Bottom-Up DPO(n)O(n)Iterative table building
4. Space-OptimizedO(n)O(1)Only need last 2 values

6. Deep Dive: Why This is the Foundation​

KEY INSIGHTS

Fibonacci teaches us:

  1. ✅ The classic recursive recurrence relation
  2. ✅ How overlapping subproblems create inefficiency
  3. ✅ The power of memoization and DP
  4. ✅ Space optimization with sliding window
  5. ✅ The pattern that underlies MANY DP problems

This is Pattern 1a in its purest form - simple accumulation without any constraints or conditions.

7. Connection to Other Problems​

FIBONACCI PATTERN APPEARS IN

Direct Applications:

  • Climbing Stairs (LC 70) - Identical structure
  • Min Cost Climbing Stairs (LC 746) - Fibonacci with costs
  • House Robber (LC 198) - Modified with max/skip logic

The Pattern:

Pure Fibonacci:    F(n) = F(n-1) + F(n-2)
Climbing Stairs:   ways[n] = ways[n-1] + ways[n-2]
Min Cost:          cost[n] = min(cost[n-1], cost[n-2]) + ...

Once you master Fibonacci, you understand the foundation of linear sequence DP!

8. Complete Implementation (Preview)​

// Space-Optimized Solution - O(n) time, O(1) space
public int fib(int n) {
    if (n <= 1) return n;

    int prev2 = 0;  // F(0)
    int prev1 = 1;  // F(1)

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

    return prev1;
}

Coming Soon​

MORE CONTENT COMING

We'll add:

  • Complete recursive solution with analysis
  • Memoized solution with execution traces
  • Bottom-up DP with detailed explanation
  • Mathematical formula approach (Binet's formula)
  • Complete complexity analysis
  • Practice problems and variations

Key Takeaways​

REMEMBER
  1. ✅ Fibonacci is the foundation of Pattern 1a
  2. ✅ Teaches the core DP concepts: recursion → memoization → iteration
  3. ✅ Space optimization: O(n) → O(1) with sliding window
  4. ✅ This pattern appears in MANY interview problems
  5. ✅ Master this, and you understand the basics of linear sequence DP

Study this problem deeply - it's the key to understanding DP!