LeetCode #509 斐波那契数
🔢 LeetCode #509 斐波那契数：动态规划入门经典
斐波那契数列是一个经典的算法问题，定义为从 0 和 1 开始，每一项是前两项之和。本文将详细解析题目，分享三种 Go 语言实现方式，帮助你从递归到动态规划逐步掌握！
📜 题目描述
来源：LeetCode #509 - Fibonacci Number
问题：
给定非负整数 n，计算斐波那契数列的第 n 项 F(n)，其中：
F(0) = 0，F(1) = 1F(n) = F(n-1) + F(n-2)，对于n > 1
示例 1
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
约束
0 <= n <= 30
💡 解题思路
核心观察
斐波那契数列的核心是状态转移方程：
F(n) = F(n-1) + F(n-2)
初始条件：
F(0) = 0F(1) = 1
这个问题可以通过递归或动态规划解决。直接递归会导致重复计算，因此我们可以使用记忆化或动态规划优化性能。
💡 小贴士：斐波那契数列广泛应用于算法问题，如爬楼梯、矩阵快速幂等。
🚀 Go 语言实现
以下是三种 Go 语言实现方式，从递归到动态规划逐步优化，适合不同场景。代码块使用 go 语法高亮，建议在富文本编辑器中启用深色主题（如 monokai 或 dracula）以增强可读性。
方法 1：递归 + 记忆化
通过递归解决，使用记忆化数组避免重复计算。
package main
import "fmt"
func fib(n int) int {
memo := make([]int, n+1)
return dfs(n, memo)
}
func dfs(n int, memo []int) int {
if n <= 1 {
return n
}
if memo[n] != 0 {
return memo[n]
}
memo[n] = dfs(n-1, memo) + dfs(n-2, memo)
return memo[n]
}
func main() {
fmt.Println(fib(2)) // 输出: 1
fmt.Println(fib(3)) // 输出: 2
fmt.Println(fib(4)) // 输出: 3
}时间复杂度：O(n)
空间复杂度：O(n)
优点：直观，易于理解递归思想
缺点：需要额外内存存储记忆化数组
方法 2：动态规划（DP 数组）
使用数组存储每个斐波那契数，迭代计算。
package main
import "fmt"
func fib(n int) int {
if n <= 1 {
return n
}
dp := make([]int, n+1)
dp[0] = 0
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
func main() {
fmt.Println(fib(4)) // 输出: 3
}时间复杂度：O(n)
空间复杂度：O(n)
优点：逻辑清晰，适合初学者理解动态规划
缺点：空间占用较多
方法 3：空间优化（滚动变量）🔥
仅用两个变量存储前两项，优化空间复杂度。
package main
import "fmt"
func fib(n int) int {
if n <= 1 {
return n
}
prev, curr := 0, 1
for i := 2; i <= n; i++ {
next := prev + curr
prev = curr
curr = next
}
return curr
}
func main() {
fmt.Println(fib(4)) // 输出: 3
}时间复杂度：O(n)
空间复杂度：O(1)
优点：高效简洁，面试最佳写法
推荐指数：⭐⭐⭐⭐⭐
📊 方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 推荐指数 |
|---|---|---|---|
| 递归 + 记忆化 | O(n) | O(n) | ⭐⭐⭐☆ |
| DP 数组 | O(n) | O(n) | ⭐⭐⭐⭐ |
| 滚动变量（最优） | O(n) | O(1) | ⭐⭐⭐⭐⭐ |
注意：对于
n <= 30，结果不会溢出 Go 的int类型。
🎯 进阶思考
扩展定义：如果初始条件变为
F(0) = 1,F(1) = 2？
需调整初始值，逻辑不变。更高效率：能否用矩阵快速幂实现 O(log n) 时间复杂度？
斐波那契数列可用矩阵形式[F(n), F(n-1)] = [[1,1],[1,0]]^(n-1) * [F(1), F(0)]优化。实际应用：斐波那契数列在爬楼梯、股票买卖等算法问题中有广泛应用。
💡 学习建议：
初学者：从递归和 DP 数组入手，理解状态转移。
进阶者：掌握滚动变量优化，体会空间优化的精髓。
高手：尝试矩阵快速幂，挑战 O(log n) 解法。
🔚 总结
斐波那契数列问题是动态规划的入门经典，核心在于状态转移方程 F(n) = F(n-1) + F(n-2)。通过三种 Go 实现（递归、DP 数组、滚动变量），我们可以从直观到高效逐步优化。
希望这篇文章帮你彻底掌握斐波那契数列！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！