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];
}
}
Input
n = 2
Output
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
};
Input
n = 2
Output
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
Input
n = 3
Output
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;
}
}
}
Input
n = 3
Output
2