斐波那契与递推数列

递推 = 状态 + 转移。理解了斐波那契，你就理解了动态规划的骨架。

四种实现：从 O(2ⁿ) 到 O(log n)

package main

import "fmt"

// 1. 朴素递归：O(2^n)，F(50) 需要计算 2^50 次
func fibNaive(n int) int {
    if n <= 1 { return n }
    return fibNaive(n-1) + fibNaive(n-2)
}

// 2. 记忆化递归：O(n)
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 { return n }
    if v, ok := memo[n]; ok { return v }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

// 3. 迭代 DP：O(n) 时间，O(1) 空间
func fibDP(n int) int {
    if n <= 1 { return n }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

// 4. 矩阵快速幂：O(log n)
// [F(n+1)]   [1 1]^n   [F(1)]
// [F(n)  ] = [1 0]   × [F(0)]
type mat [2][2]int

func matMul(a, b mat) mat {
    var c mat
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            for k := 0; k < 2; k++ {
                c[i][j] += a[i][k] * b[k][j]
            }
        }
    }
    return c
}

func matPow(m mat, n int) mat {
    result := mat{{1, 0}, {0, 1}}  // 单位矩阵
    for n > 0 {
        if n&1 == 1 { result = matMul(result, m) }
        m = matMul(m, m)
        n >>= 1
    }
    return result
}

func fibMatrix(n int) int {
    if n <= 1 { return n }
    base := mat{{1, 1}, {1, 0}}
    return matPow(base, n)[0][1]
}

func main() {
    fmt.Println(fibDP(10))       // 55
    fmt.Println(fibMatrix(10))   // 55
    fmt.Println(fibMatrix(50))   // 12586269025
}

黄金比例与增长率

斐波那契数列的相邻比 F(n+1)/F(n) 趋近于黄金比例 φ = (1+√5)/2 ≈ 1.618。这可以用特征方程求解：x² = x + 1，解为 φ = (1+√5)/2 和 ψ = (1-√5)/2，通项公式为 F(n) = (φⁿ - ψⁿ) / √5。这个公式揭示了斐波那契数列指数增长的本质。

package main

import (
    "fmt"
    "math"
)

func main() {
    phi := (1 + math.Sqrt(5)) / 2
    psi := (1 - math.Sqrt(5)) / 2

    // Binet 公式（浮点近似，大 n 会有误差）
    binetFib := func(n int) int {
        return int(math.Round((math.Pow(phi, float64(n)) - math.Pow(psi, float64(n))) / math.Sqrt(5)))
    }

    for i := 0; i <= 10; i++ {
        fmt.Printf("F(%2d) = %d\n", i, binetFib(i))
    }

    // 相邻比趋近黄金比例
    a, b := 1, 1
    for i := 0; i < 10; i++ {
        fmt.Printf("%.6f ", float64(b)/float64(a))
        a, b = b, a+b
    }
    fmt.Println()  // 1.618... 越来越精确
}

递推数列的通用框架

所有线性常系数递推都可以用矩阵快速幂加速到 O(log n)。爬楼梯问题、Tribonacci、任意 k 阶线性递推，都套同一个框架：写出转移矩阵，用矩阵快速幂求第 n 个状态向量。

斐波那契数列是数学里最美的意外——它从兔子繁殖开始，却贯穿了整个现代算法。

— 具体数学