题解 | 斐波那契数列

1、解题思路

1. 递归法：直接根据斐波那契数列的定义进行递归计算。时间复杂度：O(2^n)，空间复杂度：O(n)（递归栈深度）。不满足题目要求，但可以作为理解问题的基础。
2. 迭代法（动态规划）：使用循环和变量存储中间结果，避免重复计算。时间复杂度：O(n)，空间复杂度：O(1)。满足题目要求。
3. 矩阵快速幂法：利用矩阵快速幂将时间复杂度优化到 O(log n)。适用于对时间复杂度要求更高的场景。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int Fibonacci(int n) {
        // write code here
        if (n == 1 || n == 2) {
            return 1;
        }
        int a = 1, b = 1, c;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        // write code here
        if (n == 1 || n == 2) return 1;
        int a = 1, b = 1, c;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        # write code here
        if n == 1 or n == 2:
            return 1
        a, b = 1, 1
        for _ in range(3, n + 1):
            c = a + b
            a, b = b, c
        return b

3、复杂度分析

1. 初始条件： fib(1) = 1，fib(2) = 1。
2. 迭代过程： 使用三个变量 a、b、c 来存储中间结果。a 和 b 分别代表 fib(n-2) 和 fib(n-1)。每次迭代更新 a 和 b 的值，最终 b 即为 fib(n)。
3. 效率： 时间复杂度：O(n)，只需一次循环。空间复杂度：O(1)，只使用了常数个变量。
4. 适用性： 适用于 n 较小的情况（n ≤ 40）。如果 n 很大（如 n ≤ 10^18），可以使用矩阵快速幂法进一步优化时间复杂度到 O(log n)。