The Fibonacci sequence is defined as: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Given n, return F(n).
Example 1:
Input: 4 Output: 3
Example 2:
Input: 10 Output: 55
Constraints: 0 <= n <= 30
Input format: Single integer n.
Output format: F(n).
dynamic programming
math
recursion
amazon
google
microsoft
Run to check your code against the sample cases, or submit to run every case