878923. Fibonacci Number
Basic
Fibonacci Number
Summary
The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. This problem involves calculating a given nth Fibonacci number.
Detailed Explanation
To solve this problem, we'll use dynamic programming to efficiently calculate the nth Fibonacci number. We can start by considering a recursive approach:
- The base cases are F(0) = 0 and F(1) = 1.
- For n > 1, F(n) is the sum of F(n-1) and F(n-2).
However, this recursive approach has exponential time complexity due to repeated calculations. To optimize this, we can use dynamic programming by storing the Fibonacci numbers as we calculate them:
- Create an array
fibof size n+1 and initialize it with 0s. - Set
fib[0] = 0andfib[1] = 1. - For i from 2 to n, set
fib[i] = fib[i-1] + fib[i-2].
This dynamic programming approach has linear time complexity O(n), which is much more efficient.
Here's a step-by-step breakdown of the solution:
- Create an array
fibof size n+1 and initialize it with 0s. - Set
fib[0] = 0andfib[1] = 1. - For i from 2 to n, set
fib[i] = fib[i-1] + fib[i-2]. - Return
fib[n], which is the nth Fibonacci number.
Time complexity: O(n) Space complexity: O(n)
Optimized Solutions
Java
public int fibonacci(int n) {
if (n <= 1) return n;
int[] fib = new int[n+1];
fib[0] = 0; fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}