Đề bài
The Fibonacci sequence starts 0, 1 and each next number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 and F(1) = 1.
Implement fibonacci(n).
Input
n: The position in the sequence.
Output
Return F(n).
Ràng buộc
0 ≤ n ≤ 90
Ví dụ
Ví dụ 1
Đầu vào:
n = 10
Kết quả mong đợi:
expected = 55Đầu vào:
long long n = 10;
Kết quả mong đợi:
long long expected = 55;Đầu vào:
long n = 10;
Kết quả mong đợi:
long expected = 55;Giải thích
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
Ví dụ 2
Đầu vào:
n = 0
Kết quả mong đợi:
expected = 0Đầu vào:
long long n = 0;
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long n = 0;
Kết quả mong đợi:
long expected = 0;Giải thích
By definition F(0) = 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
The first two values are fixed, so start from the base cases.
Gợi ý 2
Build later values from the two previous ones instead of recomputing recursively.
Gợi ý 3
Use an iterative approach to avoid repeated work and deep recursion.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.