フィボナッチ数

問題

フィボナッチ数列は0, 1から始まり、次の数は直前の2つの数の和になります: 0, 1, 1, 2, 3, 5, 8, …。F(0) = 0、F(1) = 1 です。

fibonacci(n) を実装してください。

n: 数列における位置。

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;

定義より F(0) = 0 です。

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

ヒント 1

最初の2つは固定なので、基底ケースから始める。

ヒント 2

再帰で再計算せず、直前2つから次の値を作る。

ヒント 3

反復処理にすると、無駄な計算と深い再帰を避けられる。

目安の計算量

時間 O(n)、追加メモリ O(1)

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