Đề bài
The tribonacci numbers extend the Fibonacci idea to three terms: T(0) = 0, T(1) = 0, T(2) = 1, and from then on T(n) = T(n − 1) + T(n − 2) + T(n − 3). The sequence goes 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …
Implement tribonacci(n).
Input
n: The index of the term, starting at 0.
Output
Return T(n). Only the last three terms are needed at any time, so a loop with three variables is enough.
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
The terms are 0, 0, 1, 1, 2, 4, 7, 13, so 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) is the first 1 in the sequence: 1.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Return the first three terms directly.
Gợi ý 2
Keep three variables and shift them along each step.
Gợi ý 3
A recursive solution without memory repeats work and is far too slow.
Độ 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.