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