LeetCode 509. 斐波那契数

Categories:

题目描述
思路分析
1. 解法一：滚动变量（推荐）
2. 解法二：矩阵快速幂
相似题目

题目描述

✅ 509. 斐波那契数

思路分析

解法一：滚动变量（推荐）

核心思路：

斐波那契数定义：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（n >= 2）。

无需保存完整的 DP 数组，只需维护前两个状态 a 和 b，滚动更新即可。

每次迭代：新值 = a + b，然后将 a、b 向前滚动一位，直到计算到第 n 项。

相比递归避免了指数级重复计算，相比完整 DP 数组将空间压缩到 O(1)。

复杂度分析：

时间复杂度：O(n)，其中 n 为目标斐波那契数的下标，需线性遍历一次。

空间复杂度：O(1)，只使用常数个变量保存滚动状态。

class Solution {
    public int fib(int n) {
        // 处理边界：F(0) = 0, F(1) = 1
        if (n <= 1) {
            return n;
        }
        // a 表示 F(i-2)，b 表示 F(i-1)
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            // 计算当前项并滚动更新
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

func fib(n int) int {
    // 处理边界：F(0) = 0, F(1) = 1
    if n <= 1 {
        return n
    }
    // a 表示 F(i-2)，b 表示 F(i-1)
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        // 计算当前项并滚动更新
        a, b = b, a+b
    }
    return b
}

解法二：矩阵快速幂

核心思路：

斐波那契递推关系可用矩阵乘法表示： [[F(n+1)], [F(n)]] = [[1,1],[1,0]]^n * [[1], [0]]

利用快速幂将矩阵的 n 次幂压缩到 O(log n) 次矩阵乘法。

每次矩阵乘法为 2×2 固定大小，所以每次乘法耗时 O(1)。

适用于 n 极大（如 10^18）时，普通线性 DP 无法满足性能要求的场景。

复杂度分析：

时间复杂度：O(log n)，其中 n 为目标斐波那契数的下标，快速幂折半递归。

空间复杂度：O(log n)，递归调用栈深度为 O(log n)；若用迭代实现则为 O(1)。

{% raw %}

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        // 初始矩阵 [[1,1],[1,0]]
        long[][] base = {{1, 1}, {1, 0}};
        long[][] result = matPow(base, n);
        // result = base^n，F(n) 在 result[1][0] 位置
        return (int) result[1][0];
    }

    // 矩阵快速幂：计算 mat^p
    private long[][] matPow(long[][] mat, int p) {
        // 单位矩阵作为初始结果
        long[][] result = {{1, 0}, {0, 1}};
        while (p > 0) {
            // 当前位为 1 时，将当前矩阵乘入结果
            if ((p & 1) == 1) {
                result = matMul(result, mat);
            }
            // 矩阵自乘，指数折半
            mat = matMul(mat, mat);
            p >>= 1;
        }
        return result;
    }

    // 2×2 矩阵乘法
    private long[][] matMul(long[][] a, long[][] b) {
        return new long[][]{
            {a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]},
            {a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]}
        };
    }
}

{% endraw %}

{% raw %}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    // 初始矩阵 [[1,1],[1,0]]
    base := [2][2]int{{1, 1}, {1, 0}}
    result := matPow(base, n)
    // result = base^n，F(n) 在 result[1][0] 位置
    return result[1][0]
}

// matPow 计算 2×2 矩阵的 p 次幂
func matPow(mat [2][2]int, p int) [2][2]int {
    // 单位矩阵作为初始结果
    result := [2][2]int{{1, 0}, {0, 1}}
    for p > 0 {
        // 当前位为 1 时，将当前矩阵乘入结果
        if p&1 == 1 {
            result = matMul(result, mat)
        }
        // 矩阵自乘，指数折半
        mat = matMul(mat, mat)
        p >>= 1
    }
    return result
}

// matMul 执行 2×2 矩阵乘法
func matMul(a, b [2][2]int) [2][2]int {
    return [2][2]int{
        {a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]},
        {a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]},
    }
}

{% endraw %}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	动态规划 / 斐波那契变形
746. 使用最小花费爬楼梯	简单	动态规划 / 费用最优
1137. 第 N 个泰波那契数	简单	动态规划 / 三元递推
剑指 Offer 10- I. 斐波那契数列	简单	动态规划 / 取模运算
剑指 Offer 10- II. 青蛙跳台阶问题	简单	动态规划 / 斐波那契变形
198. 打家劫舍	中等	动态规划 / 线性 DP
50. Pow(x, n)	中等	数学 / 快速幂

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/18200391