斐波那契数列

📌 核心概念

斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

💻 求解方法

🎯 经典应用

💡 斐波那契性质

1. 通项公式（Binet公式）

F(n) = (φ^n - ψ^n) / √5

2. 黄金分割

lim(F(n+1) / F(n)) = φ ≈ 1.618

3. 平方和

F(n)² + F(n+1)² = F(2n+1)

4. 相邻项性质

F(n+1) * F(n-1) - F(n)² = (-1)^n

📊 方法对比

方法	时间复杂度	空间复杂度	优缺点
递归	O(2^n)	O(n)	最慢，仅适合演示
记忆化	O(n)	O(n)	简单，占用空间
DP	O(n)	O(1)	常用方法
矩阵快速幂	O(log n)	O(1)	最快，需要大数时
通项公式	O(1)	O(1)	精度问题

Go 代码

// 动态规划（空间优化）
func fib(n int) int {
    if n <= 1 {
        return n
    }
 
    prev, curr := 0, 1
 
    for i := 2; i <= n; i++ {
        prev, curr = curr, prev+curr
    }
 
    return curr
}
 
// 矩阵快速幂
func fibMatrix(n int) int {
    if n <= 1 {
        return n
    }
 
    matrix := [][]int{{1, 1}, {1, 0}}
    result := matrixPow(matrix, n)
 
    return result[0][1]
}
 
func matrixPow(matrix [][]int, n int) [][]int {
    result := [][]int{{1, 0}, {0, 1}}
 
    for n > 0 {
        if n&1 == 1 {
            result = matrixMultiply(result, matrix)
        }
        matrix = matrixMultiply(matrix, matrix)
        n >>= 1
    }
 
    return result
}
 
func matrixMultiply(A, B [][]int) [][]int {
    return [][]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]},
    }
}

🎯 经典题目

题目	LeetCode	关键点
斐波那契数	509	基础题
爬楼梯	70	变形应用
打家劫舍	198	DP优化
泰波那契数	1137	推广
使用最小花费爬楼梯	746	变形

---

返回：数学算法