Problem
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).
Einschränkungen
0 ≤ n ≤ 90
Beispiele
Beispiel 1
Eingabe:
n = 10
Erwartete Ausgabe:
expected = 55Eingabe:
long long n = 10;
Erwartete Ausgabe:
long long expected = 55;Eingabe:
long n = 10;
Erwartete Ausgabe:
long expected = 55;Erläuterung
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
Beispiel 2
Eingabe:
n = 0
Erwartete Ausgabe:
expected = 0Eingabe:
long long n = 0;
Erwartete Ausgabe:
long long expected = 0;Eingabe:
long n = 0;
Erwartete Ausgabe:
long expected = 0;Erläuterung
By definition F(0) = 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
The first two values are fixed, so start from the base cases.
Hinweis 2
Build later values from the two previous ones instead of recomputing recursively.
Hinweis 3
Use an iterative approach to avoid repeated work and deep recursion.
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.