grid47 Exploring patterns and algorithms
Sep 17, 2024
4 min read
Solution to LeetCode 509: Fibonacci Number Problem
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Given an integer n, return the nth Fibonacci number.
Problem
Approach
Steps
Complexity
Input: The input is an integer n, representing the position of the desired Fibonacci number.
Example: n = 2
Constraints:
• 0 <= n <= 30
Output: The output should be the nth Fibonacci number.
Example: 1
Constraints:
• The output should be an integer representing the nth Fibonacci number.
Goal: To compute the nth Fibonacci number efficiently using dynamic programming or iterative methods.
Steps:
• 1. Initialize an array to store Fibonacci numbers up to n.
• 2. Set the base cases F(0) = 0 and F(1) = 1.
• 3. Use a loop to calculate the Fibonacci numbers for all values up to n.
• 4. Return the value of F(n).
Goal: The value of n must be between 0 and 30 inclusive.
Steps:
• 0 <= n <= 30
Assumptions:
• The value of n will always be a non-negative integer.
• Input: n = 2
• Explanation: For n = 2, the Fibonacci sequence is [0, 1, 1], so F(2) = 1.
Approach: The approach is to use an iterative method with dynamic programming to calculate the Fibonacci numbers up to n.
Observations:
• The Fibonacci sequence can be computed using recursion, but an iterative approach is more efficient for larger values of n.
• We can use a dynamic programming approach to store previously computed Fibonacci numbers to avoid redundant calculations.
• By using an array to store intermediate results, we can compute Fibonacci numbers in linear time.
Steps:
• 1. Initialize a dp array of size n+1 to store Fibonacci numbers.
• 2. Set dp[0] = 0 and dp[1] = 1.
• 3. Loop from 2 to n, setting dp[i] = dp[i-1] + dp[i-2].
• 4. Return dp[n].
Empty Inputs:
• There are no empty inputs as n will always be an integer between 0 and 30.
Large Inputs:
• The algorithm is efficient enough to handle n up to 30, so there are no large input concerns.
Special Values:
• The base cases for F(0) and F(1) should be handled correctly.
Constraints:
• The algorithm must run in O(n) time for values of n between 0 and 30.
Defines the `fib` function that takes an integer `n` and returns the nth Fibonacci number.
2 : Base Case Check
if(n ==0) return0;
Checks the base case: if `n` is 0, return 0 since the 0th Fibonacci number is 0.
3 : Array Initialization
vector<int> dp(n +1, 0);
Initializes a dynamic programming array `dp` of size `n+1` where each element is set to 0. This array will store the Fibonacci numbers up to the nth number.
4 : Base Case Assignment
dp[0] =0;
Assigns the value 0 to the first element in the dp array, corresponding to the 0th Fibonacci number.
5 : Base Case Assignment
dp[1] =1;
Assigns the value 1 to the second element in the dp array, corresponding to the 1st Fibonacci number.
6 : Loop Start
for(int i =2; i <= n; i++)
Starts a loop from `i = 2` up to `n` to calculate the Fibonacci numbers iteratively.
7 : Fibonacci Calculation
dp[i] = dp[i -1] + dp[i -2];
Calculates the current Fibonacci number by adding the previous two Fibonacci numbers (dp[i-1] and dp[i-2]) and stores the result in dp[i].
8 : Return Statement
return dp[n];
Returns the nth Fibonacci number from the dp array.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the input number. The algorithm computes Fibonacci numbers in a linear fashion.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), due to the space required to store Fibonacci numbers in the dp array.
