LeetCode - Easy - 509. Fibonacci Number

Topic

• Math
• Dynamic Programming
• Recursion
• Memoization

Description

https://leetcode.com/problems/fibonacci-number/

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
1
2

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
1
2
3

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
1
2
3

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
1
2
3

Constraints:

• 0 <= n <= 30

Analysis

方法一：循环遍历

方法二：尾递归

动态规划解题思路

Submissions

public class FibonacciNumber {
	
	//方法一
    public int fib(int n) {
    	int first = 0, second = 1;
    	
    	for(int i = 1; i <= n; i++) {
    		int newOne = first + second;
    		first = second;
    		second = newOne;
    	}
    	
        return first;
    }

    //方法二
    public int fib2(int n) {
    	return fib2(n, 0, 1, 0);
    }
    
    private int fib2(int n, int first, int second, int count) {
    	if(n == count) {
    		return first;
    	}
    	return fib2(n, second, first + second, count + 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

Test

import static org.junit.Assert.*;
import org.junit.Test;

public class FibonacciNumberTest {

    @Test
    public void test() {
        FibonacciNumber fObj = new FibonacciNumber();
        assertEquals(1, fObj.fib(2));
        assertEquals(2, fObj.fib(3));
        assertEquals(3, fObj.fib(4));
        
        assertEquals(1, fObj.fib2(2));
        assertEquals(2, fObj.fib2(3));
        assertEquals(3, fObj.fib2(4));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18