Fibonacci Number

ID: 509; easy

Solution 1

``````class Solution {
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;

int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}

return dp[n];
}
}``````

This the bottom-up tabulation approach. We start from the very "bottom" and add up the numbers until `n`.

Time complexity: `O(n)`

Space complexity: `O(n)`

Solution 2

``````class Solution {
private Map<Integer, Integer> map = new HashMap<>();

public int fib(int n) {
if (n <= 1) return n;
map.putIfAbsent(0, 0);
map.putIfAbsent(1, 1);
if (map.containsKey(n)) {
return map.get(n);
}
map.put(n, fib(n - 1) + fib(n - 2));
return map.get(n);
}``````

This is the top-down memoization approach. We use a hash table to achieve memoization.

Time complexity: `O(n)`

Space complexity: `O(n)`

Solution 3

``````class Solution {
public int fib(int n) {
if (n <= 1) return n;
int x = 0, y = 1, z = 1;

for (int i = 3; i < n + 1; i++) {
x = y;
y = z;
z = x + y;
}
return z;
}
}
// x y z
//   x y z
// 0 1 1 2 3 5 8``````

This is the bottom-up approach without using an array to keep the results. Instead, we only use three variables to keep the progress.

Time complexity: `O(n)`

Space complexity: `O(1)`

Last updated