Fibonacci Number Solution in Python

Problem Description

Ah, the Fibonacci sequence! The mathematical equivalent of that one friend who keeps showing up uninvited to every party. You know the one: 0, 1, 1, 2, 3, 5, 8… It just keeps going! The task here is to find the nth Fibonacci number.

In simpler terms, if you were to count the number of ways to climb a staircase where you can take either one or two steps at a time, you’d be using the Fibonacci sequence. So, if you’re ever in a situation where you need to count how many ways you can avoid doing chores, just remember: it’s all about Fibonacci!

Code Solution

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n

        dp = [0, 0, 1]

        for i in range(2, n + 1):
            dp[0] = dp[1]
            dp[1] = dp[2]
            dp[2] = dp[0] + dp[1]

        return dp[2]

Approach

The code uses a dynamic programming approach to calculate the Fibonacci number. It initializes a list dp to store the last three Fibonacci numbers. The loop iterates from 2 to n, updating the list with the sum of the last two Fibonacci numbers. This way, it avoids the exponential time complexity of a naive recursive solution.

Time and Space Complexity

Time Complexity: O(n) – We iterate through the numbers from 2 to n.

Space Complexity: O(1) – We only use a fixed amount of space for the dp list.

Real-World Example

Imagine you’re trying to figure out how many different ways you can arrange your books on a shelf. If you can either place one book or two books at a time, the Fibonacci sequence will help you calculate the total arrangements. So, next time you’re organizing your bookshelf, just remember: Fibonacci is your friend!