509.斐波那契數(java)

509.斐波那契數

• 題目
• 思路
• 代碼

LeetCode筆記彙總

題目

斐波那契數，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，後面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

思路

n為0時傳回0，n為1時傳回1。

當n大于1時，傳回fib(n-1)+fib(n-2)

代碼

class Solution {
    public int fib(int n) {
        if(n == 0)  return 0;
        if(n == 1)  return 1;
        return fib(n-1)+fib(n-2);
    }
}