Đề bài
Dãy tribonacci mở rộng ý tưởng của dãy Fibonacci lên ba số hạng: T(0) = 0, T(1) = 0, T(2) = 1, và từ đó trở đi T(n) = T(n − 1) + T(n − 2) + T(n − 3). Dãy có dạng 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …
Hãy viết tribonacci(n).
Đầu vào
n: Chỉ số của số hạng, bắt đầu từ 0.
Đầu ra
Trả về T(n). Tại mỗi thời điểm chỉ cần ba số hạng cuối, nên một vòng lặp với ba biến là đủ.
Ràng buộc
0 ≤ n ≤ 74
Ví dụ
Đầu vào:
n = 7
Kết quả mong đợi:
expected = 13
Đầu vào:
long long n = 7;
Kết quả mong đợi:
long long expected = 13;
Đầu vào:
long n = 7;
Kết quả mong đợi:
long expected = 13;
Giải thích
Các số hạng là 0, 0, 1, 1, 2, 4, 7, 13, nên T(7) = 13.
Đầu vào:
n = 2
Kết quả mong đợi:
expected = 1
Đầu vào:
long long n = 2;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long n = 2;
Kết quả mong đợi:
long expected = 1;
Giải thích
T(2) là số 1 đầu tiên trong dãy: 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trả về trực tiếp ba số hạng đầu.
Gợi ý 2
Giữ ba biến và dịch chúng lên sau mỗi bước.
Gợi ý 3
Lời giải đệ quy không ghi nhớ sẽ tính lặp lại rất nhiều và chậm quá mức.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.