Problem
The Fibonacci sequence is defined as:F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)
n, return F(n).
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 6Output
8Explanation
F(0) = 0
F(1) = 1
F(2) = 0 + 1 = 1
F(3) = 1 + 1 = 2
F(4) = 1 + 2 = 3
F(5) = 2 + 3 = 5
F(6) = 3 + 5 = 8
Solution
This solution uses Dynamic Programming. The key observation is that every Fibonacci number depends on the previous two numbers:F(n) = F(n - 1) + F(n - 2)The array
dp stores the Fibonacci number at each index. We start with the base cases dp[0] = 0 and dp[1] = 1.
We then build the solution from smaller subproblems to larger ones until we reach
dp[n].
public int fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
// Base cases.
dp[0] = 0;
dp[1] = 1;
// Build each value from the previous two.
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Complexity
We calculate each Fibonacci number once, resulting inO(n) time complexity. The DP array stores n + 1 values, requiring O(n) space.
Space Optimized Approach
The DP array is useful for understanding how Dynamic Programming works, but each Fibonacci number only depends on the previous two values.Therefore, instead of storing all values, we only need two variables to represent the previous two Fibonacci numbers.
public int fib(int n) {
if (n <= 1) {
return n;
}
int previous = 0;
int current = 1;
for (int i = 2; i <= n; i++) {
int next = previous + current;
previous = current;
current = next;
}
return current;
}
Complexity
The loop still runsn times, so the time complexity remains O(n). Only a constant number of variables are used, reducing the space complexity to O(1).