LeetCode #70 爬楼梯(动态规划)
🧗♂️ LeetCode #70 爬楼梯：动态规划入门经典
假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以选择爬 1 或 2 个台阶。问：有多少种不同的方法可以爬到楼顶？
这是动态规划的经典入门题，常见于 LeetCode、算法面试和编程教学中。本文将详细解析题目，分享三种 Go 语言实现方式，并提供进阶思考，助你彻底掌握！
📜 题目描述
来源：LeetCode #70 - Climbing Stairs
问题：
每次你可以爬 1 或 2 个台阶。给定正整数 n，计算到达楼顶的不同方法数。
示例 1
输入：n = 2
输出：2
解释：
1 阶 + 1 阶
2 阶
示例 2
输入：n = 3
输出：3
解释：
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
约束
1 <= n <= 45
💡 解题思路
核心观察
要到达第 n 阶楼梯，只能从以下两种情况到达：
从第
n-1阶爬 1 步从第
n-2阶爬 2 步
因此，到达第 n 阶的方法数为：
f(n) = f(n-1) + f(n-2)
这与斐波那契数列高度相似，初始条件为：
f(1) = 1（1 种方法）f(2) = 2（2 种方法）
💡 小贴士：本题本质是斐波那契数列的变种，例如：
f(3) = 3,f(4) = 5。
🚀 Go 语言实现
以下是三种 Go 语言实现方式，从递归到动态规划，逐步优化，适合不同场景。代码块已标注语言为 go，建议在富文本编辑器中启用深色主题（如 monokai 或 dracula）以增强视觉效果。
方法 1：递归 + 记忆化
通过递归解决，使用记忆化避免重复计算。
package main
import "fmt"
func climbStairs(n int) int {
memo := make([]int, n+1)
return dfs(n, memo)
}
func dfs(n int, memo []int) int {
if n <= 2 {
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(climbStairs(2)) // 输出: 2
fmt.Println(climbStairs(3)) // 输出: 3
}时间复杂度：O(n)
空间复杂度：O(n)
优点：直观，体现递归思想
缺点：需要额外内存存储记忆化数组
方法 2：动态规划（DP 数组）
使用数组存储每个台阶的状态，迭代计算。
package main
import "fmt"
func climbStairs(n int) int {
if n <= 2 {
return n
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
func main() {
fmt.Println(climbStairs(5)) // 输出: 8
}时间复杂度：O(n)
空间复杂度：O(n)
优点：逻辑清晰，适合初学者
缺点：空间占用较多
方法 3：空间优化（滚动变量）🔥
仅用两个变量存储前两步状态，优化空间复杂度。
package main
import "fmt"
func climbStairs(n int) int {
if n <= 2 {
return n
}
prev, curr := 1, 2
for i := 3; i <= n; i++ {
next := prev + curr
prev = curr
curr = next
}
return curr
}
func main() {
fmt.Println(climbStairs(45)) // 输出: 1836311903
}时间复杂度：O(n)
空间复杂度：O(1)
优点：高效简洁，面试最佳写法
推荐指数：⭐⭐⭐⭐⭐
📊 方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 推荐指数 |
|---|---|---|---|
| 递归 + 记忆化 | O(n) | O(n) | ⭐⭐⭐☆ |
| DP 数组 | O(n) | O(n) | ⭐⭐⭐⭐ |
| 滚动变量（最优） | O(n) | O(1) | ⭐⭐⭐⭐⭐ |
注意：当
n = 45时，结果为1836311903，不会溢出 Go 的int类型。
🎯 进阶思考
扩展步长：如果每次可以爬 1、2 或 3 阶？
状态转移方程变为：f(n) = f(n-1) + f(n-2) + f(n-3)。任意步长：如果允许爬 1 到 k 阶？
类似“完全背包”问题，需调整 DP 逻辑。更高效率：能否用矩阵快速幂达到 O(log n) 时间复杂度？
斐波那契数列的矩阵形式可实现此优化。
💡 学习建议：
初学者：先掌握递归和 DP 数组写法。
进阶者：练习滚动变量优化，理解状态转移核心。
高手：尝试矩阵快速幂解法，挑战 O(log n)。
🔚 总结
“爬楼梯”问题是动态规划的入门经典，核心在于理解状态转移方程 f(n) = f(n-1) + f(n-2)。通过三种 Go 实现（递归、DP 数组、滚动变量），我们可以从直观到高效逐步优化。
希望这篇文章帮你彻底掌握爬楼梯问题！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！