斐波那契数列 - JZ07

题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n，请你输出斐波那契数列的第 n 项。

斐波那契数列是这样定义的：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), 其中 n > 1

数据范围： 1 ≤ n ≤ 40

示例：

• 输入：n = 4
• 输出：3
• 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

数列前几项： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

解题思路

斐波那契数列是动态规划的经典入门题目，有多种解法：

1. 递归法（朴素）： 直接按定义递归，但存在重复计算问题
2. 记忆化递归： 使用缓存避免重复计算
3. 动态规划（自底向上）： 从小到大计算，避免递归
4. 空间优化的DP： 只保存前两个数，O(1)空间
5. 矩阵快速幂： 高效计算大数，O(log n)时间
6. 通项公式： 数学公式直接计算

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 可能用到的辅助类型定义
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现以下函数：

• fibonacci(n int) int - 主要实现

可选实现多种解法：

• fibonacciRecursive(n int) int - 朴素递归法
• fibonacciMemo(n int) int - 记忆化递归
• fibonacciDP(n int) int - 动态规划
• fibonacciOptimized(n int) int - 空间优化DP
• fibonacciMatrix(n int) int - 矩阵快速幂
• fibonacciFormula(n int) int - 通项公式

2. 运行测试

# 运行单元测试
go test -v

# 运行基准测试
go test -bench=.

3. 检查代码格式

# 格式化代码
go fmt ./...

# 代码检查
go vet ./...

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
朴素递归	O(2^n)	O(n)	指数级时间，大量重复计算
记忆化递归	O(n)	O(n)	缓存避免重复计算
动态规划	O(n)	O(n)	自底向上计算
空间优化DP	O(n)	O(1)	只保存必要状态
矩阵快速幂	O(log n)	O(1)	最快的精确算法
通项公式	O(1)	O(1)	但有精度问题

知识点

• 递归与迭代的转换
• 动态规划思想入门
• 记忆化优化
• 状态转移方程
• 空间复杂度优化
• 矩阵快速幂
• 时间复杂度分析

扩展思考

1. 溢出问题： 当n较大时如何处理整数溢出？
2. 大数计算： 如何计算第1000项斐波那契数？
3. 相关变种： 青蛙跳台阶、矩形覆盖等问题
4. 优化策略： 不同场景下选择合适的算法