Fibonacci Sequence

Problem

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Given a number n, calculate the nth Fibonacci number.

Examples:

Example 1:
Input: n = 5
Output: 5
Explanation: The Fibonacci sequence is [0, 1, 1, 2, 3, 5, 8, ...]. F(5) = 5.

Example 2:
Input: n = 10
Output: 55
Explanation: F(10) = F(9) + F(8) = 34 + 21 = 55.

Solution

Intuition

  • The naive recursive approach to calculate Fibonacci numbers leads to exponential time complexity due to recalculating the same values multiple times.
  • Dynamic Programming can optimize this by storing previously calculated values to avoid redundant calculations.
  • We can use either a top-down approach (memoization) or a bottom-up approach (tabulation) to solve this problem efficiently.

Approach

  • Initialize an array or map to store previously calculated Fibonacci numbers.
  • For the bottom-up approach, start from the base cases (F(0) = 0, F(1) = 1) and iteratively calculate F(2), F(3), ..., F(n).
  • For the top-down approach, use recursion with memoization to calculate F(n) by checking if F(n) is already calculated before making recursive calls.
  • Return the nth Fibonacci number once calculated.

Complexity Analysis

  • Time Complexity: O(n) - We calculate each Fibonacci number exactly once.
  • Space Complexity: O(n) - We store all Fibonacci numbers from 0 to n.
Implementation
CPP
Run your code to see output here