Fibonacci

Fibonacci

Method 1(Recursion) O(2^n) 2^n nodes, each node with O(1) operation, thus total is O(2^n)

public class Solution {
public long fibonacci(int K) {
// Write your solution here
if (K < 0) {
return 0;
}
if (K == 0) {
return 0;
}
if (K == 1) {
return 1;
}
return fibonacci(K - 1) + fibonacci(K - 2);
}
}

Method2(DP) with O(n) space

public class Solution {
public long fibonacci(int K) {
// Write your solution here
if (K <= 0) {
return 0;
}
long[] array = new long[K + 1];
array[0] = 0;
array[1] = 1;
for (int i = 2; i <= K; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[K];
}
}

Method3:

O(n) 的recussion without using memorrized search.

public class Solution {

public long result = 0;
public long a = 0;
public long b = 1;
public long fibonacci(int K) {
// Write your solution here
if (K < 0) {
return 0;
}
if (K == 1) {
return 1;
}
helper(K);
return result;
}

public void helper(int n) {
if (n == 0) {
return;
}
if (n == 1) {
return;
}
helper(n - 1);
result = a + b;
a = b;
b = result;
}
}