斐波那契數(shù)列

寫一個函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項（即 F(N)）。斐波那契數(shù)列的定義如下：

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008，請返回 1。

示例

• 輸入：n = 2

• 輸出：1

提示

0 <= n <= 100

方法：動態(tài)規(guī)劃

由于斐波那契數(shù)存在遞推關(guān)系，因此可以使用動態(tài)規(guī)劃求解。動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程即為上述遞推關(guān)系，邊界條件為 F(0) 和 F(1)。

舉例說明：

F(2) = F(1) + F(0) = 1

F(3) = F(2) + F(1) = 2

F(4) = F(3) + F(2) = 3

F(5) = F(4) + F(3) = 5

由于 n 只有第 n-1 和 n-2 項有關(guān)系，所以只需要初始化三個整型變量 p、q 、r，然后用使 p 、q 交替前進，最后，p 和 q 的和取模1e9+7 即可。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(n)。

• 空間復(fù)雜度：O(1)。

寫在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。