easyRecursionDynamic programming, 1D target 15 min
Fibonacci number
The Fibonacci numbers start with F(0) = 0 and F(1) = 1. Every later one is the sum of the two before it: F(k) = F(k - 1) + F(k - 2). So the sequence begins 0, 1, 1, 2, 3, 5, 8, 13.
Write fib(n) that returns F(n) as an exact integer.
Example 1
Input
n = 6Output8F(0) through F(6) are 0, 1, 1, 2, 3, 5, 8.
Example 2
Input
n = 2Output1F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 3
Input
n = 0Output0F(0) is a starting value, so there is nothing to add.
Constraints
0 ≤ n ≤ 90
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.