題目

題目描述

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項。斐波那契數列的定義如下：

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

斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出。
答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請返回 1。

示例1

輸入：n = 2輸出：1

示例2

輸入：n = 5輸出：5

題解

遞歸

把f(n) 拆解 為f(n-1)和f(n-2)遞歸計算，以f(1)和f(0)為終止條件。
大量重復遞歸計算，會直接超時。時間復雜度：O($2^n$)空間復雜度：O(n)

class Solution:def fib(self, n: int) -> int:if n <= 0:return nreturn self.fib(n-1) + self.fib(n-2)

動態規劃

• 狀態定義：dp為一維數組，dp[i]為斐波那契數列的第i個值。
• 轉移方程：dp[i] = dp[i-1] + dp[i-2]。
• 初始狀態：dp[0] = 0, dp[1] = 1。

時間復雜度：O(n)，循環n次，每次O(1)。空間復雜度：O(n)，dp[n]占用O(n)。

class Solution:def fib(self, n: int) -> int:if n <= 0:return ndp = []dp.append(0)dp.append(1)for i in range(2, n+1):dp_tmp = (dp[i-1] + dp[i-2]) % 1000000007dp.append(dp_tmp)return dp[n]

動態規劃（空間優化）

利用 輔助變量使a, b 交替前進，節省了dp[]列表空間。 時間復雜度：O(n)，循環n次，每次O(1)。空間復雜度：O(1)，變量占用O(1)。

class Solution:def fib(self, n: int) -> int:a, b = 0, 1for _ in range(n):a, b = b, a + breturn a % 1000000007