# 0509. Fibonacci Number

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0509-fibonacci-number)

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`. That is,

```
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
```

Given `n`, calculate `F(n)`.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `0 <= n <= 30`

```
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Instead of creating a 2D DP table, **we could just rely on two variables** since this simple DP question **doesn't require too much past information.**
{% endhint %}

It is quite straightforward that **two variables store information of F(n-1) and F(n-2)** respectively. And the **initialized values are 0 and 1 respectively.**

$$
F(n) = F(n-1) + F(n-2), and\ F(0) = 0, F(1) = 1
$$
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def fib(self, n: int) -> int:
        # (base case)
        if n == 0 or n == 1: return n
        
        # ==================================================
        #  Dynamic Programming                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)

        n1, n2 = 0, 1
        for i in range(n - 1):
            n1, n2 = n2, n1 + n2
            
        return n2

```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */

    public int fib(int n) {
        /* base case */
        if(n == 0 || n == 1) return n;
        
        int first = 0, second = 1;
        
        for(int i=0 ; i<n-1 ; i++) {
            int tmp = first;
            first = second;
            second += tmp;
        }
        
        return second;
    }
}
```

{% endtab %}
{% endtabs %}