LeetCode - Algorithms - 509. Fibonacci Number

\( F_n = F_{n-1} + F_{n-2} \)

\( F_0 = 0, F_1 = F_2 = 1 \)

Problem

509. Fibonacci Number

a “toy” problem. It’s easy to understand and maybe surprising that there are many different solutions.

Java

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int N) {
        int r=0;
		if (N == 0)
			r = 0;
		if (N == 1)
			r = 1;
		if (N > 1)
			r = fib(N - 1) + fib(N - 2);
		return r;
    }
}

Submission Detail

  • 31 / 31 test cases passed.
  • Runtime: 14 ms, faster than 5.42% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.1 MB, less than 5.51% of Java online submissions for Fibonacci Number.

Dynamic Programming

Using dynamic programming in the calculation of the nth member of the Fibonacci sequence improves its performance greatly.

bottom-up approach

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int fib(int N) {
		if (N == 0)
			return 0;
		int previousFib = 0, currentFib = 1;
		int newFib = 0;
		for (int i = 1; i < N; i++) {
			newFib = previousFib + currentFib;
			previousFib = currentFib;
			currentFib = newFib;
		}
		return currentFib;        
    }
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 35.8 MB, less than 36.87% of Java online submissions for Fibonacci Number.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int N) {
		int r=0, recip1st=0, recip2nd=1;
		if (N == 0)
			r = 0;
		if (N == 1)
			r = 1;		
		for(int i=1; i<N; i++) {
			r = recip1st + recip2nd;
			recip1st = recip2nd;
			recip2nd = r;
		}
		return r;
    }
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.6 MB, less than 5.51% of Java online submissions for Fibonacci Number.

top-down approach

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int fib(int N) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 0);
		map.put(1, 1);
		map.put(2, 1);
		map.put(3, 2);
		map.put(4, 3);
		map.put(5, 5);
		map.put(6, 8);
		map.put(7, 13);
		map.put(8, 21);
		map.put(9, 34);
		map.put(10, 55);
		map.put(11, 89);
		map.put(12, 144);
		map.put(13, 233);
		map.put(14, 377);
		map.put(15, 610);
		map.put(16, 987);
		map.put(17, 1597);
		map.put(18, 2584);
		map.put(19, 4181);
		map.put(20, 6765);
		map.put(21, 10946);
		map.put(22, 17711);
		map.put(23, 28657);
		map.put(24, 46368);
		map.put(25, 75025);
		map.put(26, 121393);
		map.put(27, 196418);
		map.put(28, 317811);
		map.put(29, 514229);
		map.put(30, 832040);
		if (!map.containsKey(N))
			map.put(N, fib(N - 1) + fib(N - 2));
		return map.get(N);        
    }
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36 MB, less than 25.69% of Java online submissions for Fibonacci Number.

2

As constraints 0 <= n <= 30

1
2
3
4
5
6
class Solution {
    public int fib(int N) {
		int[] table = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
		return table[N];        
    }
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 35.7 MB, less than 69.84% of Java online submissions for Fibonacci Number.

formula

golden ratio \(\huge \varphi = \frac{1 + \sqrt{5}}{2} \)

\(\LARGE F_n = \frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}} \)

This solution is often used as a standard example of the method of generating functions.

1
2
3
4
5
6
7
class Solution {
    public int fib(int N) {
    	final double SQRT5 = Math.sqrt(5);
    	Double d = ( Math.pow((1+SQRT5)/2,N)-Math.pow((1-SQRT5)/2,N) )/SQRT5;
    	return d.intValue();
    }
}

Submission Detail

  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.2 MB, less than 5.51% of Java online submissions for Fibonacci Number.