Luna Tech | 斐波那契数（Leetcode）

January 12, 2021 字数 248 1 min

1. 题目

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

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

斐波那契数是什么

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2) => 条件：n > 1

如：

F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3

输入：数字 n 输出：结果 F(n)

2. 思路

首先判定 n 是否等于 0,1,2，特殊情况可以直接返回结果（虽然题目给的是 n > 1 的公式，但 n = 2 也是特殊情况）
假如 n > 2，从 n = 2 开始反复计算 F(n) = F(n-1)+ F(n-2) 就可以得到最终结果

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


public class Solution {
    public int Fib(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 1;

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