# Leetcode 509. Fibonacci Number 練習
> Difficulty : `Easy`
> `Java` `演算法Algorithm`

> 撰寫人[name=KVJK_2125] [time=SAT, May 18, 2024 18:10]

## 題目
### 說明 Description
EN：<br>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`. <br>That is,<br>
>F(0) = 0, F(1) = 1
>F(n) = F(n - 1) + F(n - 2), for n > 1.

Given `n`, calculate `F(n)`.

繁中：<br>斐波那契數（通常以`F(n)`表示）所形成的數列稱為 斐波那契數列。數列由`0`和`1`開始，後面的每一項數字都是前面兩個數字的和。 也就是：<br>

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

給定`n`，請計算`F(n)`。

### 範例 Example
Example 1:
> Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

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

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

### 限制條件 Constraints
- `0 <= n <= 30`

## 解題
### 思路 Intuition/Approach

- Step1.<br> 題目中指出：`F(0) = 0, F(1) = 1`<br>可知，n=0時，輸出0；n=1時，輸出1。<br> 因此建立`if(n <= 1)`時，回傳n。

- Step2.<br> 直接使用題目中的公式：`F(n) = F(n - 1) + F(n - 2)`<br>建立公式中陣列F，並設定其長度為 n+1。

- Step3.<br> 設定`F[0]`及`F[1]`為1，並設定for迴圈從2開始`for(int i = 2; i <= n; i++)`，並在迴圈中放入公式`F[i] = F[i-1] + F[i-2];`。

- Step4.<br> 最終回傳F[n-1]。
### 程式碼 Code（加註解）

class Solution {
    public int fib(int n) {
        //確認n是否小於或等於1
        if(n <= 1)
            return n;
        //建立一變數，為n長度+1
        int[] F = new int[n+1];

        //設定好'從0開始的'前兩位
        F[0] = 1;
        F[1] = 1;
        //依題目提供之公式進行計算
        for(int i = 2; i <= n; i++)
            F[i] = F[i-1] + F[i-2];
        
        //返回最終值
        return F[n-1];
    }
}