## Algorithm

Problem Name: 509. 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)`.

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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int fib(int n) {
if (n == 0) {
return 0;
}
int[] result = new int[n + 1];
result[0] = 0;
result[1] = 1;
for (int i = 2; i  < = n; i++) {
result[i] = result[i - 1] + result[i - 2];
}
return result[n];
}
}
``````
Copy The Code &

Input

cmd
n = 2

Output

cmd
1

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const cache = {}
const fib = function(N) {
if(cache[N]) return cache[N]
if(N === 0) return 0
if(N === 1) return 1
let res = fib(N - 1) + fib(N - 2)
cache[N] = res
return res
};
``````
Copy The Code &

Input

cmd
n = 2

Output

cmd
1

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def fib(self, N: int) -> int:
return self.fib(N - 1) + self.fib(N - 2) if N > 1 else N

``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
2

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0509_FibonacciNumber
{
public int Fib(int N)
{
if (N == 0) return 0;
if (N == 1) return 1;

var prev1 = 0;
var prev2 = 1;
for (int i = 2; i  <  N; i++)
{
var temp = prev1 + prev2;
prev1 = prev2;
prev2 = temp;
}

return prev1 + prev2;
}
}
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
2