Fibonacci Number

Đề bài

Dãy Fibonacci, thường ký hiệu là F(n), tạo thành một dãy được gọi là dãy Fibonacci, sao cho mỗi số là tổng của hai số trước đó, bắt đầu từ 0 và 1.

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), với n > 1

Cho n, tính F(n).

Ví dụ

Ví dụ 1:

Input: n = 2
Output: 1
Giải thích: F(2) = F(1) + F(0) = 1 + 0 = 1.

Ví dụ 2:

Input: n = 4
Output: 3
Giải thích: F(4) = F(3) + F(2) = 2 + 1 = 3.

Ràng buộc

• 0 <= n <= 30