G1 Fibonacci Sequence

介绍

斐波那契数列（Fibonacci Sequence）是一个经典的数学序列，它的定义很简单：前两个数是0和1（或1和1，取决于从哪个索引开始），此后的每个数都是前两个数的和。形式上，斐波那契数列可以表示为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n ≥ 2)。

动态规划（Dynamic Programming）是求解斐波那契数列的高效方法，核心思想是通过存储已计算的子问题解来避免重复计算。与递归实现相比，动态规划消除了大量的重复计算，将时间复杂度从指数级O(2^n)降低到线性级O(n)。

算法步骤

1. 确定边界条件：F(0) = 0, F(1) = 1

2. 创建数组或变量存储已计算的斐波那契数

3. 从小到大（自底向上）计算每个斐波那契数：F(i) = F(i-1) + F(i-2)

4. 返回F(n)作为结果

算法详解

以计算F(6)为例，详细展示动态规划的计算过程：

1. 初始化：

   • 设定F(0) = 0, F(1) = 1作为基础情况

   • 创建dp数组：dp = [0, 1, , , , , _]（下划线表示待计算的位置）

2. 自底向上计算：

   • 计算F(2) = F(1) + F(0) = 1 + 0 = 1

   • 计算F(3) = F(2) + F(1) = 1 + 1 = 2

   • 计算F(4) = F(3) + F(2) = 2 + 1 = 3

   • 计算F(5) = F(4) + F(3) = 3 + 2 = 5

   • 计算F(6) = F(5) + F(4) = 5 + 3 = 8

3. 最终dp数组：dp = [0, 1, 1, 2, 3, 5, 8]

4. 返回结果：F(6) = 8

核心特性

• 重叠子问题：多次求解相同的子问题

• 最优子结构：大问题的最优解包含小问题的最优解

• 自底向上：从小问题逐步构建大问题的解

• 时间复杂度：O(n)

• 空间复杂度：O(n)

基础实现

以下是斐波那契数列的动态规划实现，包括多种主流编程语言：

代码实现

Java实现

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        
        // 创建dp数组存储计算结果
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        // 自底向上计算
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        int n = 10;
        System.out.println("F(" + n + ") = " + fibonacci(n));
        
        System.out.println("斐波那契数列前10项：");
        for (int i = 0; i < 10; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

在上述代码中，通过：

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

实现了动态规划的核心思想，每次计算只依赖之前计算好的两个子问题的结果。

Python实现

def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    
    // 创建dp数组存储计算结果
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    // 自底向上计算
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 测试
const n = 10;
console.log(`F(${n}) = ${fibonacci(n)}`);

console.log("斐波那契数列前10项：");
console.log(Array.from({length: 10}, (_, i) => fibonacci(i)).join(" "));

优化策略

空间优化（滚动数组） Spatial optimization (rolling array)

使用有限的变量而不是整个数组存储计算状态：

public static int fibonacciOptimized(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 只需要两个变量存储前两个斐波那契数
    int prev = 0;
    int curr = 1;
    
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    
    return curr;
}

矩阵快速幂 Matrix fast power

利用矩阵乘法和快速幂，可以在O(log n)时间内计算出斐波那契数：

public static int fibonacciMatrix(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 定义斐波那契矩阵 [[1,1],[1,0]]
    int[][] F = new int[][]{{1, 1}, {1, 0}};
    
    // 计算F^(n-1)
    F = matrixPower(F, n - 1);
    
    // 结果是F^(n-1)的[0][0]元素
    return F[0][0];
}

private static int[][] matrixPower(int[][] A, int n) {
    int[][] result = new int[][]{{1, 0}, {0, 1}}; // 单位矩阵
    
    while (n > 0) {
        if ((n & 1) == 1) {
            result = multiplyMatrix(result, A);
        }
        A = multiplyMatrix(A, A);
        n >>= 1;
    }
    
    return result;
}

private static int[][] multiplyMatrix(int[][] A, int[][] B) {
    int[][] C = new int[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            C[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j];
        }
    }
    return C;
}

优缺点

优点

• 避免重复计算：每个斐波那契数只计算一次

• 高效率：时间复杂度为O(n)，远优于递归的O(2^n)

• 内存使用可优化：可以将空间复杂度降至O(1)

• 自底向上：避免了递归调用栈溢出的风险

• 易于理解和实现：动态规划思想直观表现在代码中

缺点

• 必须从头计算：无法计算单个位置的值而不计算前面所有的值

• 可能溢出：对于较大的n，容易发生整数溢出

• 基本实现需要额外空间：存储中间计算结果需要O(n)空间

• 不适合n特别大的情况：即使是O(log n)的算法，当n非常大时也可能效率不高

• 矩阵快速幂实现相对复杂：优化的算法理解和实现难度较高

应用场景

1. 计算机科学教学：作为递归和动态规划的经典案例

2. 金融模型：用于预测股市、商品价格等模式

3. 自然现象建模：描述植物生长、兔子繁殖等自然现象

4. 算法设计：优化递归算法的范例

5. 数据压缩：某些数据压缩算法利用斐波那契编码

6. 密码学：用于某些加密算法和安全系统

扩展

通项公式（Binet公式）

使用解析解直接计算斐波那契数：

public static int fibonacciBinet(int n) {
    if (n <= 0) {
        return 0;
    }
    
    double goldenRatio = (1 + Math.sqrt(5)) / 2;
    return (int)Math.round((Math.pow(goldenRatio, n) - Math.pow(1 - goldenRatio, n)) / Math.sqrt(5));
}

模运算下的周期性（Pisano周期）

当计算斐波那契数模m时，数列会表现出周期性：

public static int fibonacciModulo(int n, int m) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 计算Pisano周期
    int pisanoPeriod = findPisanoPeriod(m);
    
    // 利用周期性计算
    n = n % pisanoPeriod;
    
    int prev = 0;
    int curr = 1;
    
    for (int i = 2; i <= n; i++) {
        int next = (prev + curr) % m;
        prev = curr;
        curr = next;
    }
    
    return curr;
}

private static int findPisanoPeriod(int m) {
    int a = 0, b = 1, c;
    for (int i = 0; i < m * m; i++) {
        c = (a + b) % m;
        a = b;
        b = c;
        if (a == 0 && b == 1) {
            return i + 1;
        }
    }
    return 0;
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

1. 为什么动态规划算法在计算斐波那契数列时比递归算法更高效？

2. 滚动数组优化的时间复杂度和空间复杂度分别是多少？

3. 斐波那契数列的增长速度如何？

测验答案

1. 递归算法会重复计算相同的子问题，比如F(5)需要重复计算F(3)和F(2)，时间复杂度为O(2^n)；而动态规划算法通过存储已计算的结果避免了重复计算，时间复杂度为O(n)。

2. 滚动数组优化的时间复杂度仍为O(n)，但空间复杂度降为O(1)，因为只需要常数个变量存储状态。

3. 斐波那契数列呈指数增长，增长率接近黄金比例φ≈1.618。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的 LeetCode 题目：

• 509. 斐波那契数 - 最基础的斐波那契数计算

• 70. 爬楼梯 - 与斐波那契数列相关的经典动态规划问题

• 746. 使用最小花费爬楼梯 - 斐波那契思想的应用

• 1137. 第 N 个泰波那契数 - 斐波那契的变种

• 873. 最长的斐波那契子序列的长度 - 结合子序列和斐波那契特性的问题