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. 思路

  1. 首先判定 n 是否等于 0,1,2,特殊情况可以直接返回结果(虽然题目给的是 n > 1 的公式,但 n = 2 也是特殊情况)
  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];
    }
}

结语

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


Talk to Luna


Support Luna