尧图网站建设 
LeetCode-Go 题解509. Fibonacci Number 七种 Go 解法全解析递归、动态规划、矩阵快速幂与通项公式【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 509. Fibonacci Number 题解为基础结合 LeetCode-Go 仓库中该题的完整 Go 实现源码系统讲解斐波那契数列的递归、记忆化搜索自底向上 / 自顶向下 / 空间优化、矩阵快速幂、通项公式、协程共七种解法逐一分析时间复杂度、空间复杂度与适用场景。读完本文你将掌握同一道题在不同复杂度约束下的递进式优化思路并能把矩阵快速幂、通项公式等技巧迁移到其他递推类题目中。题目描述斐波那契数Fibonacci numbers通常记作F(n)构成一个称为斐波那契数列的序列。该序列中每个数字都是前两个数字之和序列从0和1开始F(0) 0, F(1) 1 F(N) F(N - 1) F(N - 2), 其中 N 1给定N计算F(N)。示例 1输入: 2 输出: 1 解释: F(2) F(1) F(0) 1 0 1示例 2输入: 3 输出: 2 解释: F(3) F(2) F(1) 1 1 2示例 3输入: 4 输出: 3 解释: F(4) F(3) F(2) 2 1 3注意0 ≤ N ≤ 30因此本题所有结果均在int范围内无需考虑大数溢出。解题思路总览求斐波那契数列的解法很多大的分类有四种递归直接递归指数级复杂度记忆化搜索 / 动态规划可以写成自底向上、自顶向下、优化空间复杂度三种变体矩阵快速幂利用矩阵乘法将递推转化为幂运算时间复杂度降到 O(log n)通项公式比奈公式本质是求 a^b还可以用快速幂进一步优化。仓库中 509. Fibonacci Number.go 恰好给出了从fib到fib6共7 个实现覆盖了上述全部思路并额外收录了一个协程版反例用于说明在算法题中启动 goroutine 的开销。下文逐一对每种解法做源码级拆解。解法一直接递归指数级仅作基线// 解法一 递归法 时间复杂度 O(2^n)空间复杂度 O(n) func fib(N int) int { if N 1 { return N } return fib(N-1) fib(N-2) }这是最直观、最贴合递推定义的写法F(N) F(N-1) F(N-2)基线条件是N 1时直接返回N。复杂度分析时间复杂度 O(2^n)每次调用会分裂成两个子调用形成一棵近似满二叉树节点数随 n 指数增长空间复杂度 O(n)来自递归调用栈的最大深度。问题所在子问题被重复计算。例如fib(5)会分别计算fib(3)两次、fib(2)三次。N 稍大如 N40时就已经难以在合理时间内完成。该写法在本仓库中仅作为性能基线存在实际做题时强烈不推荐。解法二自底向上的记忆化搜索DP 表// 解法二 自底向上的记忆化搜索 时间复杂度 O(n)空间复杂度 O(n) func fib1(N int) int { if N 1 { return N } cache : map[int]int{0: 0, 1: 1} for i : 2; i N; i { cache[i] cache[i-1] cache[i-2] } return cache[N] }自底向上bottom-up的思路是既然F(N)依赖更小的下标那就从最小的子问题开始按顺序把所有中间结果算出来并缓存。用map[int]int也可以换成切片[]int下标访问更快作为缓存表初始化F(0)0、F(1)1从i2循环到N每一步都利用前两个已算好的值最终cache[N]就是答案。复杂度分析每个i只计算一次时间复杂度 O(n)缓存表存了n1个值空间复杂度 O(n)。相比直接递归以空间换时间彻底消除了重复计算。解法三自顶向下的记忆化搜索Memoization// 解法三 自顶向下的记忆化搜索 时间复杂度 O(n)空间复杂度 O(n) func fib2(N int) int { if N 1 { return N } return memoize(N, map[int]int{0: 0, 1: 1}) } func memoize(N int, cache map[int]int) int { if _, ok : cache[N]; ok { return cache[N] } cache[N] memoize(N-1, cache) memoize(N-2, cache) return memoize(N, cache) }自顶向下top-down则保留递归的外形但引入备忘录memo每次计算前先查缓存命中则直接返回未命中才递归求解并在返回前把结果写入缓存。值得注意的一个实现细节memoize在写入cache[N]之后又调用了一次memoize(N, cache)此时由于缓存已命中会直接返回cache[N]本质上等价于return cache[N]。这种写法保证了入口处的一致性但读者可以按更常见的写法理解为if _, ok : cache[N]; ok { return cache[N] } cache[N] memoize(N-1, cache) memoize(N-2, cache) return cache[N]复杂度分析每个子问题最多计算一次时间复杂度 O(n)缓存表与递归栈合计空间复杂度 O(n)。解法四优化版 DP滚动变量空间 O(1)// 解法四 优化版的 dp节约内存空间 时间复杂度 O(n)空间复杂度 O(1) func fib3(N int) int { if N 1 { return N } if N 2 { return 1 } current, prev1, prev2 : 0, 1, 1 for i : 3; i N; i { current prev1 prev2 prev2 prev1 prev1 current } return current }观察递推式可以发现计算F(i)只需要F(i-1)和F(i-2)两个值更早的结果不再需要保留。因此可以用三个变量滚动推进把空间复杂度从 O(n) 降到 O(1)。边界处理N 1返回NN 2时F(2) F(1) F(0) 1循环从i 3开始prev1、prev2分别保存F(i-1)、F(i-2)每轮用current prev1 prev2推进再同步滚动两个前驱变量。复杂度分析时间复杂度仍为 O(n)空间复杂度 O(1)。这是迭代法中最推荐的工程写法——时间线性、空间常数且无递归栈溢出风险。解法五矩阵快速幂O(log n)// 解法五 矩阵快速幂 时间复杂度 O(log n)空间复杂度 O(log n) // | 1 1 | ^ n | F(n1) F(n) | // | 1 0 | | F(n) F(n-1) | func fib4(N int) int { if N 1 { return N } var A [2][2]int{ {1, 1}, {1, 0}, } A matrixPower(A, N-1) return A[0][0] } func matrixPower(A [2][2]int, N int) [2][2]int { if N 1 { return A } A matrixPower(A, N/2) A multiply(A, A) var B [2][2]int{ {1, 1}, {1, 0}, } if N%2 ! 0 { A multiply(A, B) } return A } func multiply(A [2][2]int, B [2][2]int) [2][2]int { x : A[0][0]*B[0][0] A[0][1]*B[1][0] y : A[0][0]*B[0][1] A[0][1]*B[1][1] z : A[1][0]*B[0][0] A[1][1]*B[1][0] w : A[1][0]*B[0][1] A[1][1]*B[1][1] A[0][0] x A[0][1] y A[1][0] z A[1][1] w return A }矩阵快速幂的数学基础是如下恒等式| 1 1 | ^ n | F(n1) F(n) | | 1 0 | | F(n) F(n-1) |于是求F(N)转化为求转移矩阵[[1,1],[1,0]]的N-1次幂取结果矩阵的[0][0]元素即可因为[0][0] F(N)。实现要点matrixPower采用二分幂思想先递归求A^(N/2)再平方得到A^N若N为奇数则额外乘一次转移矩阵Bmultiply完成 2×2 矩阵乘法依次计算四个元素x、y、z、w递归深度为 O(log n)因此空间复杂度 O(log n)。复杂度分析时间复杂度 O(log n)空间复杂度 O(log n)。当 N 很大远超本题 30 的上限时这是最优算法也是快速幂思想在递推数列中的经典应用。解法六通项公式比奈公式黄金分割// 解法六 公式法 f(n)(1/√5)*{[(1√5)/2]^n -[(1-√5)/2]^n}时间复杂度在 O(log n) 和 O(n) 之间空间复杂度 O(1) // 经过实际测试会发现 pow() 系统函数比快速幂慢说明 pow() 比 O(log n) 慢 // 斐波那契数列是一个自然数的数列通项公式却是用无理数来表达的。而且当 n 趋向于无穷大时前一项与后一项的比值越来越逼近黄金分割 0.618或者说后一项与前一项的比值小数部分越来越逼近 0.618。 // 斐波那契数列用计算机计算的时候可以直接用四舍五入函数 Round 来计算。 func fib5(N int) int { var goldenRatio float64 float64((1 math.Sqrt(5)) / 2) return int(math.Round(math.Pow(goldenRatio, float64(N)) / math.Sqrt(5))) }斐波那契数列虽然每一项都是自然数却存在一个用无理数表达的通项公式比奈公式F(N) (1/√5) * { [(1√5)/2]^N - [(1-√5)/2]^N }由于第二项[(1-√5)/2]^N的绝对值随 N 增大迅速趋近于 0计算机实现时可以只保留主项goldenRatio^N / √5再四舍五入goldenRatio (1 √5) / 2 ≈ 1.618即黄金分割比math.Pow(goldenRatio, N) / math.Sqrt(5)后用math.Round取整即可得到精确的F(N)。复杂度分析空间复杂度 O(1)时间复杂度取决于math.Pow的实现源码注释与实测结论表明它介于 O(log n) 与 O(n) 之间——系统库的pow()比手写的快速幂更慢说明其在常数或实现细节上并非严格 O(log n)。注意该解法依赖浮点运算当 N 很大时可能因浮点精度误差导致结果错误。本题0 ≤ N ≤ 30的约束下精度完全可靠但推广到超大 N 时需谨慎此时矩阵快速幂是更稳妥的选择。解法七协程版反例不推荐// 解法七 协程版但是时间特别慢不推荐放在这里只是告诉大家写 LeetCode 算法题的时候启动 goroutine 特别慢 func fib6(N int) int { return -fibb(N) } func fibb(n int) -chan int { result : make(chan int) go func() { defer close(result) if n 1 { result - n return } result - -fibb(n-1) -fibb(n-2) }() return result }仓库特意收录了第七个版本用 goroutine 和 channel 模拟递归。每个fibb(n)都启动一个 goroutine内部再分别启动两个 goroutine 递归计算fibb(n-1)与fibb(n-2)通过 channel 传回结果。该版本本质上仍是递归 重复计算且叠加了goroutine 创建与 channel 通信的巨大开销。源码注释明确指出时间特别慢不推荐使用收录它的目的是告诉大家写 LeetCode 算法题时启动 goroutine 特别慢并发并不总是性能的解药。这个反例对于理解 Go 并发的代价很有教学价值但在实际刷题与工程计算斐波那契数时切勿采用。测试验证100% 用例覆盖仓库为本题提供了完整的表驱动测试 509. Fibonacci Number_test.gofunc Test_Problem509(t *testing.T) { qs : []question509{ {para509{1}, ans509{1}}, {para509{2}, ans509{1}}, {para509{3}, ans509{2}}, {para509{4}, ans509{3}}, // 如需多个测试可以复制上方元素。 } for _, q : range qs { _, p : q.ans509, q.para509 // 覆盖全部解法fib2 经 memoize、fib4 经 matrixPower/multiply、fib6 经 fibb 间接覆盖 fmt.Printf(【input】:%v 【output】:%v %v %v %v %v %v %v\n, p, fib(p.one), fib1(p.one), fib2(p.one), fib3(p.one), fib4(p.one), fib5(p.one), fib6(p.one)) } }测试用例覆盖N 1, 2, 3, 4预期输出分别为1, 1, 2, 3与题目给出的示例完全一致。关键设计在于一次遍历同时调用全部七种解法分别验证fib、fib1、fib2、fib3、fib4、fib5、fib6的输出测试注释明确说明了间接覆盖路径fib2经memoize覆盖、fib4经matrixPower/multiply覆盖、fib6经fibb覆盖即主函数之外的辅助函数也全部被测试执行到这正是 LeetCode-Go 项目宣称 100% test coverage 的具体体现之一。若要在本地运行该用例可在仓库根目录执行go test ./leetcode/0509.Fibonacci-Number/ -v -run Test_Problem509七种解法复杂度对比总结解法函数核心思路时间复杂度空间复杂度推荐度一fib直接递归O(2^n)O(n)不推荐仅作基线二fib1自底向上 DP 表O(n)O(n)常用三fib2自顶向下记忆化O(n)O(n)常用四fib3滚动变量优化 DPO(n)O(1)强烈推荐迭代最优五fib4矩阵快速幂O(log n)O(log n)大 N 最优六fib5通项公式黄金分割O(log n)~O(n)O(1)依赖浮点精度七fib6goroutine 协程极慢高反例勿用小结与延伸通过 LeetCode 509 这道题可以从五个维度完整地理解斐波那契数列递归 → 记忆化解决重复子问题把指数级降到线性DP 表 → 滚动变量观察状态依赖关系把空间从 O(n) 压到 O(1)递推 → 矩阵幂把线性递推改写成矩阵乘幂用快速幂把时间降到 O(log n)递推 → 通项公式数学层面一步到位但要警惕浮点精度边界并发陷阱goroutine 的调度与 channel 通信开销在递归场景下远大于收益。矩阵快速幂、通项公式等技巧不止适用于本题——凡是满足F(N) a*F(N-1) b*F(N-2)形式的线性递推数列如爬楼梯、铺瓷砖、汉诺塔变体等都可以复用同一套思路。完整可运行的源码与测试见 leetcode/0509.Fibonacci-Number 目录仓库中 1400 道题均采用同样的题解 源码 测试结构可作为系统刷题与复习的参考。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：509. Fibonacci Number 七种 Go 解法全解析（递归、动态规划、矩阵快速幂与通项公式）
LeetCode-Go 题解509. Fibonacci Number 七种 Go 解法全解析递归、动态规划、矩阵快速幂与通项公式【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 509. Fibonacci Number 题解为基础结合 LeetCode-Go 仓库中该题的完整 Go 实现源码系统讲解斐波那契数列的递归、记忆化搜索自底向上 / 自顶向下 / 空间优化、矩阵快速幂、通项公式、协程共七种解法逐一分析时间复杂度、空间复杂度与适用场景。读完本文你将掌握同一道题在不同复杂度约束下的递进式优化思路并能把矩阵快速幂、通项公式等技巧迁移到其他递推类题目中。题目描述斐波那契数Fibonacci numbers通常记作F(n)构成一个称为斐波那契数列的序列。该序列中每个数字都是前两个数字之和序列从0和1开始F(0) 0, F(1) 1 F(N) F(N - 1) F(N - 2), 其中 N 1给定N计算F(N)。示例 1输入: 2 输出: 1 解释: F(2) F(1) F(0) 1 0 1示例 2输入: 3 输出: 2 解释: F(3) F(2) F(1) 1 1 2示例 3输入: 4 输出: 3 解释: F(4) F(3) F(2) 2 1 3注意0 ≤ N ≤ 30因此本题所有结果均在int范围内无需考虑大数溢出。解题思路总览求斐波那契数列的解法很多大的分类有四种递归直接递归指数级复杂度记忆化搜索 / 动态规划可以写成自底向上、自顶向下、优化空间复杂度三种变体矩阵快速幂利用矩阵乘法将递推转化为幂运算时间复杂度降到 O(log n)通项公式比奈公式本质是求 a^b还可以用快速幂进一步优化。仓库中 509. Fibonacci Number.go 恰好给出了从fib到fib6共7 个实现覆盖了上述全部思路并额外收录了一个协程版反例用于说明在算法题中启动 goroutine 的开销。下文逐一对每种解法做源码级拆解。解法一直接递归指数级仅作基线// 解法一 递归法 时间复杂度 O(2^n)空间复杂度 O(n) func fib(N int) int { if N 1 { return N } return fib(N-1) fib(N-2) }这是最直观、最贴合递推定义的写法F(N) F(N-1) F(N-2)基线条件是N 1时直接返回N。复杂度分析时间复杂度 O(2^n)每次调用会分裂成两个子调用形成一棵近似满二叉树节点数随 n 指数增长空间复杂度 O(n)来自递归调用栈的最大深度。问题所在子问题被重复计算。例如fib(5)会分别计算fib(3)两次、fib(2)三次。N 稍大如 N40时就已经难以在合理时间内完成。该写法在本仓库中仅作为性能基线存在实际做题时强烈不推荐。解法二自底向上的记忆化搜索DP 表// 解法二 自底向上的记忆化搜索 时间复杂度 O(n)空间复杂度 O(n) func fib1(N int) int { if N 1 { return N } cache : map[int]int{0: 0, 1: 1} for i : 2; i N; i { cache[i] cache[i-1] cache[i-2] } return cache[N] }自底向上bottom-up的思路是既然F(N)依赖更小的下标那就从最小的子问题开始按顺序把所有中间结果算出来并缓存。用map[int]int也可以换成切片[]int下标访问更快作为缓存表初始化F(0)0、F(1)1从i2循环到N每一步都利用前两个已算好的值最终cache[N]就是答案。复杂度分析每个i只计算一次时间复杂度 O(n)缓存表存了n1个值空间复杂度 O(n)。相比直接递归以空间换时间彻底消除了重复计算。解法三自顶向下的记忆化搜索Memoization// 解法三 自顶向下的记忆化搜索 时间复杂度 O(n)空间复杂度 O(n) func fib2(N int) int { if N 1 { return N } return memoize(N, map[int]int{0: 0, 1: 1}) } func memoize(N int, cache map[int]int) int { if _, ok : cache[N]; ok { return cache[N] } cache[N] memoize(N-1, cache) memoize(N-2, cache) return memoize(N, cache) }自顶向下top-down则保留递归的外形但引入备忘录memo每次计算前先查缓存命中则直接返回未命中才递归求解并在返回前把结果写入缓存。值得注意的一个实现细节memoize在写入cache[N]之后又调用了一次memoize(N, cache)此时由于缓存已命中会直接返回cache[N]本质上等价于return cache[N]。这种写法保证了入口处的一致性但读者可以按更常见的写法理解为if _, ok : cache[N]; ok { return cache[N] } cache[N] memoize(N-1, cache) memoize(N-2, cache) return cache[N]复杂度分析每个子问题最多计算一次时间复杂度 O(n)缓存表与递归栈合计空间复杂度 O(n)。解法四优化版 DP滚动变量空间 O(1)// 解法四 优化版的 dp节约内存空间 时间复杂度 O(n)空间复杂度 O(1) func fib3(N int) int { if N 1 { return N } if N 2 { return 1 } current, prev1, prev2 : 0, 1, 1 for i : 3; i N; i { current prev1 prev2 prev2 prev1 prev1 current } return current }观察递推式可以发现计算F(i)只需要F(i-1)和F(i-2)两个值更早的结果不再需要保留。因此可以用三个变量滚动推进把空间复杂度从 O(n) 降到 O(1)。边界处理N 1返回NN 2时F(2) F(1) F(0) 1循环从i 3开始prev1、prev2分别保存F(i-1)、F(i-2)每轮用current prev1 prev2推进再同步滚动两个前驱变量。复杂度分析时间复杂度仍为 O(n)空间复杂度 O(1)。这是迭代法中最推荐的工程写法——时间线性、空间常数且无递归栈溢出风险。解法五矩阵快速幂O(log n)// 解法五 矩阵快速幂 时间复杂度 O(log n)空间复杂度 O(log n) // | 1 1 | ^ n | F(n1) F(n) | // | 1 0 | | F(n) F(n-1) | func fib4(N int) int { if N 1 { return N } var A [2][2]int{ {1, 1}, {1, 0}, } A matrixPower(A, N-1) return A[0][0] } func matrixPower(A [2][2]int, N int) [2][2]int { if N 1 { return A } A matrixPower(A, N/2) A multiply(A, A) var B [2][2]int{ {1, 1}, {1, 0}, } if N%2 ! 0 { A multiply(A, B) } return A } func multiply(A [2][2]int, B [2][2]int) [2][2]int { x : A[0][0]*B[0][0] A[0][1]*B[1][0] y : A[0][0]*B[0][1] A[0][1]*B[1][1] z : A[1][0]*B[0][0] A[1][1]*B[1][0] w : A[1][0]*B[0][1] A[1][1]*B[1][1] A[0][0] x A[0][1] y A[1][0] z A[1][1] w return A }矩阵快速幂的数学基础是如下恒等式| 1 1 | ^ n | F(n1) F(n) | | 1 0 | | F(n) F(n-1) |于是求F(N)转化为求转移矩阵[[1,1],[1,0]]的N-1次幂取结果矩阵的[0][0]元素即可因为[0][0] F(N)。实现要点matrixPower采用二分幂思想先递归求A^(N/2)再平方得到A^N若N为奇数则额外乘一次转移矩阵Bmultiply完成 2×2 矩阵乘法依次计算四个元素x、y、z、w递归深度为 O(log n)因此空间复杂度 O(log n)。复杂度分析时间复杂度 O(log n)空间复杂度 O(log n)。当 N 很大远超本题 30 的上限时这是最优算法也是快速幂思想在递推数列中的经典应用。解法六通项公式比奈公式黄金分割// 解法六 公式法 f(n)(1/√5)*{[(1√5)/2]^n -[(1-√5)/2]^n}时间复杂度在 O(log n) 和 O(n) 之间空间复杂度 O(1) // 经过实际测试会发现 pow() 系统函数比快速幂慢说明 pow() 比 O(log n) 慢 // 斐波那契数列是一个自然数的数列通项公式却是用无理数来表达的。而且当 n 趋向于无穷大时前一项与后一项的比值越来越逼近黄金分割 0.618或者说后一项与前一项的比值小数部分越来越逼近 0.618。 // 斐波那契数列用计算机计算的时候可以直接用四舍五入函数 Round 来计算。 func fib5(N int) int { var goldenRatio float64 float64((1 math.Sqrt(5)) / 2) return int(math.Round(math.Pow(goldenRatio, float64(N)) / math.Sqrt(5))) }斐波那契数列虽然每一项都是自然数却存在一个用无理数表达的通项公式比奈公式F(N) (1/√5) * { [(1√5)/2]^N - [(1-√5)/2]^N }由于第二项[(1-√5)/2]^N的绝对值随 N 增大迅速趋近于 0计算机实现时可以只保留主项goldenRatio^N / √5再四舍五入goldenRatio (1 √5) / 2 ≈ 1.618即黄金分割比math.Pow(goldenRatio, N) / math.Sqrt(5)后用math.Round取整即可得到精确的F(N)。复杂度分析空间复杂度 O(1)时间复杂度取决于math.Pow的实现源码注释与实测结论表明它介于 O(log n) 与 O(n) 之间——系统库的pow()比手写的快速幂更慢说明其在常数或实现细节上并非严格 O(log n)。注意该解法依赖浮点运算当 N 很大时可能因浮点精度误差导致结果错误。本题0 ≤ N ≤ 30的约束下精度完全可靠但推广到超大 N 时需谨慎此时矩阵快速幂是更稳妥的选择。解法七协程版反例不推荐// 解法七 协程版但是时间特别慢不推荐放在这里只是告诉大家写 LeetCode 算法题的时候启动 goroutine 特别慢 func fib6(N int) int { return -fibb(N) } func fibb(n int) -chan int { result : make(chan int) go func() { defer close(result) if n 1 { result - n return } result - -fibb(n-1) -fibb(n-2) }() return result }仓库特意收录了第七个版本用 goroutine 和 channel 模拟递归。每个fibb(n)都启动一个 goroutine内部再分别启动两个 goroutine 递归计算fibb(n-1)与fibb(n-2)通过 channel 传回结果。该版本本质上仍是递归 重复计算且叠加了goroutine 创建与 channel 通信的巨大开销。源码注释明确指出时间特别慢不推荐使用收录它的目的是告诉大家写 LeetCode 算法题时启动 goroutine 特别慢并发并不总是性能的解药。这个反例对于理解 Go 并发的代价很有教学价值但在实际刷题与工程计算斐波那契数时切勿采用。测试验证100% 用例覆盖仓库为本题提供了完整的表驱动测试 509. Fibonacci Number_test.gofunc Test_Problem509(t *testing.T) { qs : []question509{ {para509{1}, ans509{1}}, {para509{2}, ans509{1}}, {para509{3}, ans509{2}}, {para509{4}, ans509{3}}, // 如需多个测试可以复制上方元素。 } for _, q : range qs { _, p : q.ans509, q.para509 // 覆盖全部解法fib2 经 memoize、fib4 经 matrixPower/multiply、fib6 经 fibb 间接覆盖 fmt.Printf(【input】:%v 【output】:%v %v %v %v %v %v %v\n, p, fib(p.one), fib1(p.one), fib2(p.one), fib3(p.one), fib4(p.one), fib5(p.one), fib6(p.one)) } }测试用例覆盖N 1, 2, 3, 4预期输出分别为1, 1, 2, 3与题目给出的示例完全一致。关键设计在于一次遍历同时调用全部七种解法分别验证fib、fib1、fib2、fib3、fib4、fib5、fib6的输出测试注释明确说明了间接覆盖路径fib2经memoize覆盖、fib4经matrixPower/multiply覆盖、fib6经fibb覆盖即主函数之外的辅助函数也全部被测试执行到这正是 LeetCode-Go 项目宣称 100% test coverage 的具体体现之一。若要在本地运行该用例可在仓库根目录执行go test ./leetcode/0509.Fibonacci-Number/ -v -run Test_Problem509七种解法复杂度对比总结解法函数核心思路时间复杂度空间复杂度推荐度一fib直接递归O(2^n)O(n)不推荐仅作基线二fib1自底向上 DP 表O(n)O(n)常用三fib2自顶向下记忆化O(n)O(n)常用四fib3滚动变量优化 DPO(n)O(1)强烈推荐迭代最优五fib4矩阵快速幂O(log n)O(log n)大 N 最优六fib5通项公式黄金分割O(log n)~O(n)O(1)依赖浮点精度七fib6goroutine 协程极慢高反例勿用小结与延伸通过 LeetCode 509 这道题可以从五个维度完整地理解斐波那契数列递归 → 记忆化解决重复子问题把指数级降到线性DP 表 → 滚动变量观察状态依赖关系把空间从 O(n) 压到 O(1)递推 → 矩阵幂把线性递推改写成矩阵乘幂用快速幂把时间降到 O(log n)递推 → 通项公式数学层面一步到位但要警惕浮点精度边界并发陷阱goroutine 的调度与 channel 通信开销在递归场景下远大于收益。矩阵快速幂、通项公式等技巧不止适用于本题——凡是满足F(N) a*F(N-1) b*F(N-2)形式的线性递推数列如爬楼梯、铺瓷砖、汉诺塔变体等都可以复用同一套思路。完整可运行的源码与测试见 leetcode/0509.Fibonacci-Number 目录仓库中 1400 道题均采用同样的题解 源码 测试结构可作为系统刷题与复习的参考。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考