Fibonacci Number

問題

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).

n: The position in the sequence.

Return F(n).

0 ≤ n ≤ 90

例 1

入力：
n = 10

期待される出力：
expected = 55

入力：
long long n = 10;

期待される出力：
long long expected = 55;

入力：
long n = 10;

期待される出力：
long expected = 55;

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.

例 2

入力：
n = 0

期待される出力：
expected = 0

入力：
long long n = 0;

期待される出力：
long long expected = 0;

入力：
long n = 0;

期待される出力：
long expected = 0;

By definition F(0) = 0.

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

The first two values are fixed, so start from the base cases.

ヒント 2

Build later values from the two previous ones instead of recomputing recursively.

ヒント 3

Use an iterative approach to avoid repeated work and deep recursion.

目安の計算量

O(n) time, O(1) extra space

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。