Nth Fibonacci Number | Introduction to Dynamic Programming

Given a non-negative integer n, your task is to find the nth Fibonacci number.

The Fibonacci sequence is a sequence where the next term is the sum of the previous two terms. The first two terms of the Fibonacci sequence are 0 followed by 1. The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21.

Here’s the [Problem Link] to begin with.

The Fibonacci sequence is defined as follows:

• F(0) = 0
• F(1) = 1
• F(n) = F(n – 1) + F(n – 2) for n > 1

Examples :

Input: n = 5
Output: 5
Explanation: The 5th Fibonacci number is 5.

Input: n = 0
Output: 0 
Explanation: The 0th Fibonacci number is 0.

Input: n = 1
Output: 1
Explanation: The 1st Fibonacci number is 1.

Constraints:
0 ≤ n ≤ 30

Solution 1: Brute Force Approach (Pure Recursion)

Intuition

Think of this like following a family tree where each person has exactly two parents! The most natural way to calculate the nth Fibonacci number is to directly implement the mathematical definition using recursion. Just like the definition says F(n) = F(n-1) + F(n-2), we make recursive calls to get these two values and add them together. It’s like asking “What’s my value?” and the answer is “Go ask my two parents what their values are, then add them up!” This continues until we reach the ancestors F(0) and F(1) who know their values directly.

Detailed Approach

1. Base Cases: If n ≤ 1, return n directly (F(0) = 0, F(1) = 1).
2. Recursive Case: For n ≥ 2, return fib(n-1) + fib(n-2).
3. Direct Implementation: Translate the mathematical definition directly into code.
4. No Optimization: Make fresh recursive calls every time, even if we’ve calculated the same value before.
5. Tree Structure: Creates a binary tree of recursive calls with massive redundancy.

Code

class Solution:
    def fib(self, num):
        # Base cases: F(0) = 0, F(1) = 1
        if num <= 1:
            return num
        
        # Recursive case: F(n) = F(n-1) + F(n-2)
        return self.fib(num - 1) + self.fib(num - 2)

    def nthFibonacci(self, n: int) -> int:
        return self.fib(n)

Code Explanation

This solution is the most straightforward translation of the Fibonacci definition into code. The fib function handles the base cases where n ≤ 1 by returning n directly (this covers both F(0) = 0 and F(1) = 1). For any other value, it makes two recursive calls to get the previous two Fibonacci numbers and adds them together. The main function nthFibonacci simply calls the helper function. This approach creates a binary tree of recursive calls, where each node represents a function call.

Dry Run

Let’s trace through: n = 5

graph TD
    Root["fib(5)<br/>Check: 5 <= 1? No<br/>Compute fib(4) + fib(3)"]
    
    %% Level 1: F(5) branches to F(4) and F(3)
    Root --- A["fib(4)<br/>Check: 4 <= 1? No<br/>Compute fib(3) + fib(2)"]
    Root --- B["fib(3)<br/>Check: 3 <= 1? No<br/>Compute fib(2) + fib(1)"]
    
    %% Level 2: F(4) branches to F(3) and F(2)
    A --- A1["fib(3)<br/>Check: 3 <= 1? No<br/>Compute fib(2) + fib(1)"]
    A --- A2["fib(2)<br/>Check: 2 <= 1? No<br/>Compute fib(1) + fib(0)"]
    
    %% Level 2: F(3) branches to F(2) and F(1)
    B --- B1["fib(2)<br/>Check: 2 <= 1? No<br/>Compute fib(1) + fib(0)"]
    B --- B2["fib(1)<br/>Check: 1 <= 1? Yes<br/>Return 1"]
    
    %% Level 3: F(3) from F(4) branches to F(2) and F(1)
    A1 --- A1a["fib(2)<br/>Check: 2 <= 1? No<br/>Compute fib(1) + fib(0)"]
    A1 --- A1b["fib(1)<br/>Check: 1 <= 1? Yes<br/>Return 1"]
    
    %% Level 3: F(2) from F(4) branches to F(1) and F(0)
    A2 --- A2a["fib(1)<br/>Check: 1 <= 1? Yes<br/>Return 1"]
    A2 --- A2b["fib(0)<br/>Check: 0 <= 1? Yes<br/>Return 0"]
    
    %% Level 3: F(2) from F(3) branches to F(1) and F(0)
    B1 --- B1a["fib(1)<br/>Check: 1 <= 1? Yes<br/>Return 1"]
    B1 --- B1b["fib(0)<br/>Check: 0 <= 1? Yes<br/>Return 0"]
    
    %% Level 4: F(2) from A1 branches to F(1) and F(0)
    A1a --- A1a1["fib(1)<br/>Check: 1 <= 1? Yes<br/>Return 1"]
    A1a --- A1a2["fib(0)<br/>Check: 0 <= 1? Yes<br/>Return 0"]
    
    %% Results bubble up
    A2a --- A2Result["F(2) = 1 + 0 = 1"]
    A2b --- A2Result
    A2Result --- A_A2["Return 1 to F(4)"]
    
    B1a --- B1Result["F(2) = 1 + 0 = 1"]
    B1b --- B1Result
    B1Result --- B_B1["Return 1 to F(3)"]
    
    A1a1 --- A1aResult["F(2) = 1 + 0 = 1"]
    A1a2 --- A1aResult
    A1aResult --- A1_A1a["Return 1 to F(3)"]
    
    A1b --- A1_A1b["Return 1 to F(3)"]
    A1_A1a --- A1Result["F(3) = 1 + 1 = 2"]
    A1_A1b --- A1Result
    A1Result --- A_A1["Return 2 to F(4)"]
    
    B2 --- B_B2["Return 1 to F(3)"]
    B_B1 --- BResult["F(3) = 1 + 1 = 2"]
    B_B2 --- BResult
    BResult --- B_Final["Return 2 to F(5)"]
    
    A_A1 --- AResult["F(4) = 2 + 1 = 3"]
    A_A2 --- AResult
    AResult --- A_Final["Return 3 to F(5)"]
    
    A_Final --- Final["F(5) = 3 + 2 = 5"]
    B_Final --- Final
    Final --- Answer["Final Answer: 5"]

    %% Styling
    style B2 fill:#90EE90
    style A2a fill:#90EE90
    style A2b fill:#90EE90
    style B1a fill:#90EE90
    style B1b fill:#90EE90
    style A1a1 fill:#90EE90
    style A1a2 fill:#90EE90
    style A1b fill:#90EE90
    style Answer fill:#90EE90
    
    style A2Result fill:#87CEEB
    style B1Result fill:#87CEEB
    style A1aResult fill:#87CEEB
    style A1Result fill:#87CEEB
    style BResult fill:#87CEEB
    style AResult fill:#87CEEB
    style Final fill:#87CEEB
    
    style Root fill:#E6E6FA

For detailed dry run [Click here]

Notice: fib(3), fib(2), fib(1), fib(0) are calculated multiple times!

Time and Space Complexity

• Time Complexity: O(2^n) – Each call branches into 2 more calls, creating exponential growth
• Space Complexity: O(n) – Maximum depth of recursion stack equals n

Simplifying It

This approach is like asking your family tree for information but having a very forgetful family – every time you ask great-grandma her age, she forgets and has to ask her parents again, even if you just asked her 5 minutes ago! Very natural but extremely wasteful.

Solution 2: Memoization Approach (Top-Down Dynamic Programming)

Intuition

What if we gave our forgetful family a notebook to write down answers so they don’t have to recalculate them? Memoization is exactly that – we store the results of expensive function calls and return the cached result when the same inputs occur again. Instead of recalculating fib(2) multiple times, we calculate it once, store the result, and look it up instantly next time. It’s like having a smart assistant who remembers previous calculations and can instantly tell you “Oh, you asked for fib(3) before – the answer is 2!”

Detailed Approach

1. Create Memoization Array: Initialize a dp array of size n+1 with -1 (indicating uncomputed).
2. Check Cache First: Before computing, check if dp[num] != -1. If so, return cached result.
3. Compute and Store: If not cached, compute recursively and store in dp[num].
4. Same Recursive Structure: Keep the same recursive logic but add caching layer.
5. One-Time Computation: Each fib(k) is computed exactly once, then reused.

Code

class Solution:
    def fib(self, num, dp):
        # Base cases: F(0) = 0, F(1) = 1
        if num <= 1:
            return num
        
        # Check if already computed (memoized)
        if dp[num] != -1:
            return dp[num]  # Return cached result
        
        # Compute and store in cache
        dp[num] = self.fib(num - 1, dp) + self.fib(num - 2, dp)
        return dp[num]

    def nthFibonacci(self, n: int) -> int:
        # Initialize memoization array with -1 (uncomputed)
        dp = [-1] * (n + 1)
        return self.fib(n, dp)

Code Explanation

This solution adds a memoization layer to the recursive approach. The dp array acts as our cache, initialized with -1 to indicate uncomputed values. Before making recursive calls, we check if dp[num] != -1 – if true, we return the cached result immediately. If not cached, we compute the value recursively and store it in dp[num] before returning. This ensures each Fibonacci number is calculated exactly once, dramatically reducing the number of recursive calls from exponential to linear.

Dry Run

Let’s trace through: n = 5

graph TD
    Root["fib(5, dp=[-1,-1,-1,-1,-1,-1])<br/>Check: 5 <= 1? No<br/>Check: dp[5] != -1? No (dp[5]=-1)<br/>Compute fib(4) + fib(3)"]
    
    %% Level 1: F(5) branches to F(4) and F(3)
    Root --- A["fib(4, dp)<br/>Check: 4 <= 1? No<br/>Check: dp[4] != -1? No (dp[4]=-1)<br/>Compute fib(3) + fib(2)"]
    Root --- B["fib(3, dp)<br/>Check: 3 <= 1? No<br/>Check: dp[3] != -1? Yes (dp[3]=2)<br/>Return dp[3] = 2 (Cache Hit!)"]
    
    %% Level 2: F(4) branches to F(3) and F(2)
    A --- A1["fib(3, dp)<br/>Check: 3 <= 1? No<br/>Check: dp[3] != -1? No (dp[3]=-1)<br/>Compute fib(2) + fib(1)"]
    A --- A2["fib(2, dp)<br/>Check: 2 <= 1? No<br/>Check: dp[2] != -1? Yes (dp[2]=1)<br/>Return dp[2] = 1 (Cache Hit!)"]
    
    %% Level 3: F(3) branches to F(2) and F(1)
    A1 --- A1a["fib(2, dp)<br/>Check: 2 <= 1? No<br/>Check: dp[2] != -1? No (dp[2]=-1)<br/>Compute fib(1) + fib(0)"]
    A1 --- A1b["fib(1, dp)<br/>Check: 1 <= 1? Yes<br/>Return 1 (Base Case)"]
    
    %% Level 4: F(2) branches to F(1) and F(0) 
    A1a --- A1a1["fib(1, dp)<br/>Check: 1 <= 1? Yes<br/>Return 1 (Base Case)"]
    A1a --- A1a2["fib(0, dp)<br/>Check: 0 <= 1? Yes<br/>Return 0 (Base Case)"]
    
    %% Results bubble up with memoization
    A1a1 --- A1aResult["F(2) = 1 + 0 = 1<br/>Store: dp[2] = 1<br/>Return 1"]
    A1a2 --- A1aResult
    A1aResult --- A1_A1a["Return 1 to F(3)"]
    
    A1b --- A1_A1b["Return 1 to F(3)"]
    A1_A1a --- A1Result["F(3) = 1 + 1 = 2<br/>Store: dp[3] = 2<br/>Return 2"]
    A1_A1b --- A1Result
    A1Result --- A_A1["Return 2 to F(4)"]
    
    A2 --- A_A2["Return 1 (from cache)"]
    A_A1 --- AResult["F(4) = 2 + 1 = 3<br/>Store: dp[4] = 3<br/>Return 3"]
    A_A2 --- AResult
    AResult --- A_Final["Return 3 to F(5)"]
    
    B --- B_Final["Return 2 (from cache)"]
    
    A_Final --- Final["F(5) = 3 + 2 = 5<br/>Store: dp[5] = 5<br/>Return 5"]
    B_Final --- Final
    Final --- Answer["Final Answer: 5<br/>dp = [0, 1, 1, 2, 3, 5]"]

    %% Styling
    style A1b fill:#90EE90
    style A1a1 fill:#90EE90
    style A1a2 fill:#90EE90
    style Answer fill:#90EE90
    
    style A1aResult fill:#87CEEB
    style A1Result fill:#87CEEB
    style AResult fill:#87CEEB
    style Final fill:#87CEEB
    style B fill:#87CEEB
    style A2 fill:#87CEEB
    
    style Root fill:#E6E6FA

For detailed dry run [Click here]

Time and Space Complexity

• Time Complexity: O(n) – Each fib(k) for k from 0 to n is computed exactly once
• Space Complexity: O(n) – dp array of size n+1 plus O(n) recursion stack

Simplifying It

This approach is like giving everyone in your family tree a notebook where they write down their answers. The first time grandma calculates her value, she writes it down. Next time anyone asks, she just reads from her notebook instead of asking her parents again!

Solution 3: Tabulation Approach (Bottom-Up Dynamic Programming)

Intuition

Instead of starting from the top (asking for fib(n)) and working our way down to base cases, what if we start from the bottom (the base cases we know) and build our way up? Tabulation is like filling out a table row by row, where each row depends only on the previous rows we’ve already filled. We start with F(0) = 0 and F(1) = 1, then systematically compute F(2), F(3), F(4)… up to F(n). It’s like building a pyramid where each level is built on the solid foundation of the levels below it.

Detailed Approach

1. Handle Base Cases: Return n directly if n ≤ 1.
2. Initialize DP Array: Create dp array of size n+1, set dp = 0, dp = 1.
3. Bottom-Up Filling: For i from 2 to n, compute dp[i] = dp[i-1] + dp[i-2].
4. Sequential Order: Fill the array in increasing order so dependencies are always ready.
5. No Recursion: Pure iterative approach eliminates recursion stack overhead.

Code

class Solution:
    def nthFibonacci(self, n: int) -> int:
        # Handle base cases
        if n <= 1:
            return n
        
        # Initialize DP array
        dp = [0] * (n + 1)
        dp[0] = 0  # F(0) = 0
        dp[1] = 1  # F(1) = 1
        
        # Fill array bottom-up
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]  # F(i) = F(i-1) + F(i-2)
        
        return dp[n]

Code Explanation

This solution eliminates recursion entirely by building the solution from the ground up. We first handle the base cases directly. Then we create a dp array and initialize the known values dp = 0 and dp = 1. The for loop fills the array from index 2 to n, where each dp[i] is computed using the previously computed values dp[i-1] and dp[i-2]. Since we fill the array sequentially, these dependencies are always available when we need them. This approach is more space and time efficient than memoization because it avoids recursion overhead.

Dry Run

Let’s trace through: n = 5

graph TD
    Root["nthFibonacci(5)<br/>Check: 5 <= 1? No<br/>Initialize dp = [0,0,0,0,0,0] (size 6)"]
    
    %% Initialization
    Root --- Init["Base Case Setup<br/>dp[0] = 0 (F(0) = 0)<br/>dp[1] = 1 (F(1) = 1)<br/>dp = [0,1,0,0,0,0]"]
    
    %% Loop iterations
    Init --- Loop["for i in range(2, 6):<br/>Fill dp array bottom-up"]
    
    %% Iteration i=2
    Loop --- I2["i=2: Compute F(2)<br/>dp[2] = dp[1] + dp[0]<br/>dp[2] = 1 + 0 = 1<br/>dp = [0,1,1,0,0,0]"]
    
    %% Iteration i=3
    I2 --- I3["i=3: Compute F(3)<br/>dp[3] = dp[2] + dp[1]<br/>dp[3] = 1 + 1 = 2<br/>dp = [0,1,1,2,0,0]"]
    
    %% Iteration i=4
    I3 --- I4["i=4: Compute F(4)<br/>dp[4] = dp[3] + dp[2]<br/>dp[4] = 2 + 1 = 3<br/>dp = [0,1,1,2,3,0]"]
    
    %% Iteration i=5
    I4 --- I5["i=5: Compute F(5)<br/>dp[5] = dp[4] + dp[3]<br/>dp[5] = 3 + 2 = 5<br/>dp = [0,1,1,2,3,5]"]
    
    %% Final result
    I5 --- Final["Loop Complete<br/>Return dp[5] = 5"]
    Final --- Answer["Final Answer: 5<br/>Complete DP Array: [0,1,1,2,3,5]"]

    %% Show dependency relationships
    I2 --- Dep2a["Uses: dp[1]=1"]
    I2 --- Dep2b["Uses: dp[0]=0"]
    
    I3 --- Dep3a["Uses: dp[2]=1 (computed)"]
    I3 --- Dep3b["Uses: dp[1]=1 (base)"]
    
    I4 --- Dep4a["Uses: dp[3]=2 (computed)"]
    I4 --- Dep4b["Uses: dp[2]=1 (computed)"]
    
    I5 --- Dep5a["Uses: dp[4]=3 (computed)"]
    I5 --- Dep5b["Uses: dp[3]=2 (computed)"]

    %% Styling
    style Answer fill:#90EE90
    style Final fill:#90EE90
    
    style I2 fill:#87CEEB
    style I3 fill:#87CEEB
    style I4 fill:#87CEEB
    style I5 fill:#87CEEB
    
    style Dep2a fill:#FFE4B5
    style Dep2b fill:#FFE4B5
    style Dep3a fill:#FFE4B5
    style Dep3b fill:#FFE4B5
    style Dep4a fill:#FFE4B5
    style Dep4b fill:#FFE4B5
    style Dep5a fill:#FFE4B5
    style Dep5b fill:#FFE4B5
    
    style Root fill:#E6E6FA
    style Init fill:#E6E6FA

For detailed dry run [Click here]

Time and Space Complexity

• Time Complexity: O(n) – Single loop from 2 to n, each iteration is O(1)
• Space Complexity: O(n) – dp array of size n+1, no recursion stack

Simplifying It

This approach is like building a staircase step by step – you place the first step (F(0)), then the second step (F(1)), then for each new step you only need to look at the two steps directly below it to know how high to build it. Very systematic and efficient!

Solution 4: Space-Optimized Tabulation (Optimal Approach)

Intuition

Looking at our tabulation approach, do we really need to store ALL the Fibonacci numbers from 0 to n? Actually, to calculate any Fibonacci number, we only need the previous two numbers! It’s like climbing stairs where you only need to remember the height of the last two steps to determine the height of the next step. This insight allows us to reduce our space usage from O(n) to O(1) by keeping track of only the last two computed values instead of the entire array.

Detailed Approach

1. Handle Base Cases: Return n directly if n ≤ 1.
2. Two Variables: Use prev2 = F(0) = 0 and prev = F(1) = 1.
3. Sliding Window: For each new Fibonacci number, compute curr = prev + prev2.
4. Update Variables: Slide the window by setting prev2 = prev, prev = curr.
5. Constant Space: Only store 2-3 variables regardless of input size.

Code

class Solution:
    def nthFibonacci(self, n: int) -> int:
        # Handle base cases
        if n <= 1:
            return n
        
        # Initialize the first two Fibonacci numbers
        prev2 = 0  # F(0)
        prev = 1   # F(1)
        
        # Compute from F(2) to F(n)
        for i in range(2, n + 1):
            curr = prev + prev2  # F(i) = F(i-1) + F(i-2)
            prev2 = prev         # Slide window: F(i-2) becomes F(i-1)
            prev = curr          # Slide window: F(i-1) becomes F(i)
        
        return prev  # prev now contains F(n)

Code Explanation

This optimal solution uses the key insight that we only need the last two Fibonacci numbers to compute the next one. We maintain two variables: prev2 (representing F(i-2)) and prev (representing F(i-1)). In each iteration, we compute the current Fibonacci number as curr = prev + prev2, then slide our “window” by updating prev2 = prev and prev = curr. This creates a sliding window effect where we always maintain the two most recent values. After the loop, prev contains F(n). This approach has the same time complexity as tabulation but uses only constant extra space.

Dry Run

Let’s trace through: n = 5

Initial: prev2 = 0 (F(0)), prev = 1 (F(1))

i = 2:

• curr = prev + prev2 = 1 + 0 = 1 (this is F(2))
• prev2 = prev = 1, prev = curr = 1
• State: prev2 = 1 (F(1)), prev = 1 (F(2))

i = 3:

• curr = prev + prev2 = 1 + 1 = 2 (this is F(3))
• prev2 = prev = 1, prev = curr = 2
• State: prev2 = 1 (F(2)), prev = 2 (F(3))

i = 4:

• curr = prev + prev2 = 2 + 1 = 3 (this is F(4))
• prev2 = prev = 2, prev = curr = 3
• State: prev2 = 2 (F(3)), prev = 3 (F(4))

i = 5:

• curr = prev + prev2 = 3 + 2 = 5 (this is F(5))
• prev2 = prev = 3, prev = curr = 5
• State: prev2 = 3 (F(4)), prev = 5 (F(5))

Return prev = 5

Time and Space Complexity

• Time Complexity: O(n) – Single loop from 2 to n, each iteration is O(1)
• Space Complexity: O(1) – Only using 3 variables regardless of input size

Simplifying It

This approach is like being a very memory-efficient climber who only remembers the heights of the last two steps they climbed. As they climb each new step, they forget the older steps but always remember the two most recent ones, which is all they need to determine the next step’s height!

Summary

The space-optimized tabulation is clearly the best approach for production use, offering optimal time complexity with minimal space usage. However, each approach teaches valuable concepts:

• Pure Recursion shows the natural mathematical definition
• Memoization introduces the concept of caching expensive computations
• Tabulation demonstrates systematic bottom-up problem solving
• Space Optimization shows how to identify and eliminate unnecessary storage

The progression from exponential recursion to optimal O(n) time and O(1) space beautifully illustrates the power of dynamic programming optimization techniques!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.