Leetcode 509 - 斐波那契数

2021-01-12

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) 就可以得到最终结果

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];
    }
}

结语

欢迎大家分享更好的解法~