Problem
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.
Einschränkungen
0 ≤ n ≤ 74
Beispiele
Eingabe:
n = 7
Erwartete Ausgabe:
expected = 13
Eingabe:
long long n = 7;
Erwartete Ausgabe:
long long expected = 13;
Eingabe:
long n = 7;
Erwartete Ausgabe:
long expected = 13;
Erläuterung
The terms are 0, 0, 1, 1, 2, 4, 7, 13, so T(7) = 13.
Eingabe:
n = 2
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 2;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 2;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
T(2) is the first 1 in the sequence: 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Return the first three terms directly.
Hinweis 2
Keep three variables and shift them along each step.
Hinweis 3
A recursive solution without memory repeats work and is far too slow.
Erwartete Komplexität
O(n) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.