Fibonacci Number
Easy · dynamic programming
The Fibonacci numbers are a sequence where each number is the sum of the two before it. The sequence starts with F(0) = 0 and F(1) = 1, and after that F(n) = F(n - 1) + F(n - 2). The first few numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21.
Given a whole number n, return F(n).
Examples
Example 1
Input: n = 4
Output: 3
F(2) = 1, F(3) = 2, so F(4) = F(3) + F(2) = 2 + 1 = 3.
Example 2
Input: n = 7
Output: 13
The sequence is 0, 1, 1, 2, 3, 5, 8, 13, so F(7) = 13.
Example 3
Input: n = 0
Output: 0
Constraints
- 0 <= n <= 30