LeetCode: 509 Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3

问题

斐波那契数，通常表示为 F(n)，形成一个序列，称为斐波那契数列，其中每个数字是前两个数字的和，起始数字是 0 和 1。即：

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), 对于 n > 1。

给定 n，计算 F(n)。

解决方案

动态规划和递归

Approach 1: Dynamic Programming (Bottom-Up) / 动态规划（自底向上）

This is a typical dynamic programming problem where we can compute the Fibonacci sequence iteratively. Using a bottom-up approach, we start with the base cases and build up to the desired Fibonacci number. We only need to store the last two values, thus optimizing the space complexity.

这是一个典型的动态规划问题，我们可以迭代地计算斐波那契数列。使用自底向上的方法，我们从基本情况开始，逐步构建到所需的斐波那契数。我们只需要存储最后两个值，从而优化了空间复杂度。

Implementation / 实现

Python

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1

        prev1, prev2 = 1, 0
        for i in range(2, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

Explanation / 解释

1. Base Cases / 基本情况

   if n == 0:
      return 0
   if n == 1:
      return 1

   • English: If n is 0, return 0. If n is 1, return 1. These are the base cases of the Fibonacci sequence.
   • Chinese: 如果 n 是 0，则返回 0；如果 n 是 1，则返回 1。这是斐波那契数列的基本情况。

2. Initialize Variables / 初始化变量

   prev1, prev2 = 1, 0

   • English: We initialize two variables prev1 for F(n-1) and prev2 for F(n-2) to keep track of the last two Fibonacci numbers.
   • Chinese: 我们初始化两个变量 prev1 表示 F(n-1)，prev2 表示 F(n-2)，用于跟踪最后两个斐波那契数。

3. Iterate to Compute Fibonacci / 迭代计算斐波那契数

   for i in range(2, n + 1):
      current = prev1 + prev2
      prev2 = prev1
      prev1 = current

   • English: For each i from 2 to n, compute the Fibonacci number as the sum of prev1 and prev2. Update prev2 and prev1 accordingly.
   • Chinese: 对于从 2 到 n 的每个 i，将斐波那契数计算为 prev1 和 prev2 之和。相应更新 prev2 和 prev1。

4. Return the Result / 返回结果

   return prev1

   • English: After the loop completes, prev1 holds the Fibonacci number for n, so we return it.
   • Chinese: 循环完成后，prev1 保存了 n 的斐波那契数，因此我们返回它。

Approach 2: Recursive with Memoization / 递归加备忘录

Recursive solutions are intuitive but inefficient without optimization due to repeated calculations. Using memoization, we store previously computed Fibonacci values, thus avoiding redundant calculations and significantly improving performance.

递归解决方案直观但效率低下，因为会有重复计算。通过使用备忘录，我们存储先前计算的斐波那契值，从而避免冗余计算，并显著提高性能。

Python

class Solution:
    def __init__(self):
        self.memo = {}

    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n not in self.memo:
            self.memo[n] = self.fib(n - 1) + self.fib(n - 2)
        return self.memo[n]

Explanation / 解释

1. Memoization Initialization / 初始化备忘录

   def __init__(self):
      self.memo = {}

   • English: We initialize a memo dictionary to store previously computed Fibonacci numbers.
   • Chinese: 我们初始化一个 memo 字典，用于存储先前计算的斐波那契数。

2. Base Cases / 基本情况

   if n == 0:
      return 0
   if n == 1:
      return 1

   • English: The base cases remain the same. If n is 0, return 0. If n is 1, return 1.
   • Chinese: 基本情况保持不变。如果 n 是 0，则返回 0；如果 n 是 1，则返回 1。

3. Recursive Calculation with Memoization / 递归计算加备忘录

   if n not in self.memo:
      self.memo[n] = self.fib(n - 1) + self.fib(n - 2)

   • English: If n is not already in memo, recursively compute fib(n-1) and fib(n-2), and store the result in memo.
   • Chinese: 如果 memo 中没有 n，则递归计算 fib(n-1) 和 fib(n-2)，并将结果存储在 memo 中。

4. Return the Memoized Result / 返回备忘录中的结果

   return self.memo[n]

   • English: Return the memoized result for n once it’s computed.
   • Chinese: 一旦计算出 n 的结果，返回备忘录中的结果。

Recursive Approach (Without Memoization) / 递归方法（不带备忘录）

This is the simplest approach but the least efficient, as it recalculates Fibonacci numbers multiple times.

这是最简单的方法，但效率最低，因为它多次重新计算斐波那契数。

Python

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

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度:

  • Dynamic Programming: O(n), as we compute each Fibonacci number once.
  • Memoized Recursion: O(n), as we memoize previously computed values.
  • Simple Recursion: O(2^n), as it recalculates Fibonacci numbers repeatedly.

• Space Complexity / 空间复杂度:

  • Dynamic Programming: O(1), using two variables to store the last two values.
  • Memoized Recursion: O(n), due to the recursion stack and memoization.
  • Simple Recursion: O(n), due to the recursion stack.

Key Concept / 关键概念

• Fibonacci Sequence / 斐波那契数列: The Fibonacci sequence is a classic example of a problem where dynamic programming or memoization can significantly reduce time complexity by avoiding redundant calculations.
• 斐波那契数列: 斐波那契数列是一个经典的问题示例，动态规划或备忘录可以通过避免冗余计算显著降低时间

复杂度。

Summary / 总结

• English: The Fibonacci sequence problem is well-suited to dynamic programming or memoization techniques. Iterative solutions using two variables can further optimize space complexity.
• Chinese: 斐波那契数列问题非常适合使用动态规划或备忘录技术。使用两个变量的迭代解决方案可以进一步优化空间复杂度。

Tips / 提示

• English: Practice identifying when problems involve overlapping subproblems (like Fibonacci numbers) and apply dynamic programming or memoization to optimize performance.
• Chinese: 练习识别何时问题涉及重叠子问题（如斐波那契数），并应用动态规划或备忘录来优化性能。

Solution Template for Similar Questions / 提示

• English: For problems involving sequences or recursive calculations, consider dynamic programming or memoization to avoid recalculating values.
• Chinese: 对于涉及序列或递归计算的问题，考虑使用动态规划或备忘录来避免重复计算。

5 More Similar Questions / 推荐5问题

1. LeetCode 70. Climbing Stairs
2. LeetCode 1137. N-th Tribonacci Number
3. LeetCode 91. Decode Ways
4. LeetCode 198. House Robber
5. LeetCode 746. Min Cost Climbing Stairs

Recommended Resources / 推荐资源

• English: Practice problems that involve recursive calculations to strengthen your understanding of dynamic programming and memoization techniques.
• Chinese: 练习涉及递归计算的问题，以加强对动态规划和备忘录技术的理解。