What is the Fibonacci Number problem pattern?

It follows a state transition dynamic programming pattern where F(n) = F(n-1) + F(n-2).

Can I solve Fibonacci Number with plain recursion?

Yes, but naive recursion has O(2^n) time complexity and will fail for larger n without memoization.

How do I optimize Fibonacci Number computation?

Use iterative DP or memoization to reduce time complexity to O(n) and consider two-variable iteration to reduce space to O(1).

What are common mistakes in Fibonacci Number interviews?

Common mistakes include missing base cases, redundant recursion, and overusing space for simple iterative solutions.

Is memoization always better than iterative for Fibonacci Number?

Memoization helps clarify recursion logic, but iterative DP is often faster and uses less space, making it more efficient for large n.

#509

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。示例 1： …

数学动态规划递归记忆化

题目描述

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

lightbulb

解题思路

方法一：递推

我们定义两个变量 $a$ 和 $b$ ，初始时 $a = 0$ , $b = 1$ 。

接下来，我们进行 $n$ 次循环，每次循环中，我们将 $a$ 和 $b$ 的值分别更新为 $b$ 和 $a + b$ 。

最后，返回 $a$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为题目给定的整数 $n$ 。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

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

speed

复杂度分析

指标	值
时间	complexity depends on the approach: naive recursion is O(2^n), memoized recursion and iterative DP are O(n). Space complexity ranges from O(n) for DP array or memoization to O(1) for space-optimized iteration.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect correct handling of base cases F(0) and F(1).
question_mark
Check whether the candidate avoids redundant recursive calls using memoization.
question_mark
Watch for space optimization in iterative solutions for follow-up questions.

warning

常见陷阱

外企场景

error
Naive recursion without memoization causes exponential time complexity and stack overflow for larger n.
error
Incorrectly handling base cases leads to off-by-one errors in sequence values.
error
Using unnecessary extra space when a simple two-variable iteration suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute Fibonacci modulo 10^9+7 to test large n handling and modular arithmetic.
arrow_right_alt
Return the first n Fibonacci numbers as an array to test iterative DP comprehension.
arrow_right_alt
Implement a recursive Fibonacci with limited stack depth using tail recursion to explore optimization.

help

常见问题

外企场景

继续练习

#241 为运算表达式设计优先级 #486 预测赢家 #464 我能赢吗