题目链接：Fibonacci
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...f(n) = f(n-1) + f(n-2)
f(1) = 0, f(2) = 1
Recursion Solution:
public int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Runtime: exponential, 2^n.
Space: O(n), stack layers
Recursion with memory
passed with 1620 ms
public int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
int[] mem = new int[n];
Arrays.fill(mem, -1);
mem[0] = 0;
mem[1] = 1;
return fibonacciHelper(n, mem);
}
private int fibonacciHelper(int n, int[] mem) {
if (mem[n - 1] >= 0) {
return mem[n - 1];
}
int res = fibonacciHelper(n - 1, mem) + fibonacciHelper(n - 2, mem);
mem[n - 1] = res;
return res;
}
Runtime: O(n)
Space: O(n)
DP solution
passed with 1563 ms
public int fibonacci(int n) {
int first = 0;
int second = 1;
if (n == 1) {
return first;
}
if (n == 2) {
return second;
}
int res = 0;
for (int i = 3; i <= n; i++) {
res = first + second;
first = second;
second = res;
}
return res;
}
Runtime: O(n)
Space: O(1)
