Golang | Leetcode Golang题解之第70题爬楼梯
Golang | Leetcode Golang题解之第70题爬楼梯
一、背景与问题
LeetCode第70题“爬楼梯”是经典的动态规划入门题。题目描述为：假设你正在爬楼梯，需要n步才能到达顶部。每次你可以爬1或2个台阶。请计算有多少种不同的方法可以到达楼顶。
这个问题看似简单，但隐藏着丰富的算法思维层次。其本质是斐波那契数列的变体，但需要考虑边界条件和性能优化。通过本篇文章，我们将深入探讨其算法原理、实现方式、性能优化以及实际应用场景。
二、基本原理
1. 数学建模
问题可以转化为求斐波那契数列的第n+1项。因为：
- n=1时，方法数=1（1步）
- n=2时，方法数=2（1+1或2步）
- n=3时，方法数=3（1+1+1, 1+2, 2+1）
- ...
- 递推公式：f(n) = f(n-1) + f(n-2)
2. 算法分类
常见解法包括：
- 递归法（指数级时间复杂度）
- 迭代法（线性时间复杂度）
- 动态规划（线性时间复杂度）
- 空间优化的动态规划（常数空间复杂度）
- 矩阵快速幂法（对数时间复杂度）
3. 算法复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归 | O(2^n) | O(n) | 小规模测试 |
| 迭代 | O(n) | O(1) | 常规场景 |
| 动态规划 | O(n) | O(n) | 大规模数据 |
| 空间优化 | O(n) | O(1) | 空间敏感场景 |
| 矩阵快速幂 | O(log n) | O(1) | 极大n值计算 |
三、环境准备
# 安装Go环境（假设已安装）
# 创建项目结构
mkdir staircase-problem
cd staircase-problem
touch main.go四、核心实现
1. 递归实现（不推荐）
package main
import "fmt"
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
return climbStairs(n-1) + climbStairs(n-2)
}
func main() {
fmt.Println(climbStairs(5)) // 输出8
}关键代码解释：
- 递归调用栈深度与n成正比
- 时间复杂度呈指数增长，n=40时会栈溢出
- 错误示例：未处理n=0的情况
2. 迭代实现（推荐）
package main
import "fmt"
func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
a, b := 1, 2
for i := 2; i < n; i++ {
a, b = b, a+b
}
return b
}
func main() {
fmt.Println(climbStairs(5)) // 输出8
}关键代码解释：
- 使用双变量保存前两个状态
- 时间复杂度O(n)，空间复杂度O(1)
- 处理了n=0的边界情况
3. 空间优化的动态规划
package main
import "fmt"
func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
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(climbStairs(5)) // 输出8
}关键代码解释：
- 使用数组保存所有中间结果
- 适合需要缓存中间结果的场景
- 空间复杂度O(n)
五、完整案例
1. Web服务接口实现
package main
import (
"fmt"
"net/http"
"strconv"
)
func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
a, b := 1, 2
for i := 2; i < n; i++ {
a, b = b, a+b
}
return b
}
func main() {
http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
nStr := r.URL.Query().Get("n")
if nStr == "" {
fmt.Fprintf(w, "Missing parameter n")
return
}
n, err := strconv.Atoi(nStr)
if err != nil {
fmt.Fprintf(w, "Invalid parameter n")
return
}
result := climbStairs(n)
fmt.Fprintf(w, "Result: %d", result)
})
http.ListenAndServe(":8080", nil)
}运行示例：
访问 http://localhost:8080/?n=5 将返回 Result: 8
实际应用场景：
- 用于计算不同步数的组合方案
- 可扩展为计算爬楼梯的不同路径数
- 需要处理大量并发请求时可考虑缓存
六、源码解析
以迭代实现为例，逐行分析：
func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
a, b := 1, 2
for i := 2; i < n; i++ {
a, b = b, a+b
}
return b
}- 处理n=0的特殊情况（通常不会出现）
- 处理n=1的特殊情况
- 初始化前两个状态a=1（n=1），b=2（n=2）
- 循环计算n>=3时的解
- 每次迭代更新a和b的值，保持a始终是前一个状态，b是当前状态
七、进阶使用
1. 矩阵快速幂法（对数时间复杂度）
package main
import (
"fmt"
"math"
)func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
// 矩阵快速幂计算斐波那契数
return fib(n + 1)
}
func fib(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
// 构造变换矩阵 [[1,1],[1,0]]
matrix := [][]int{{1, 1}, {1, 0}}
result := matrixPower(matrix, n-1)
return result[0][0]
}
func matrixPower(mat [][]int, power int) [][]int {
// 初始化结果矩阵为单位矩阵
res := [][]int{{1, 0}, {0, 1}}
for power > 0 {
if power%2 == 1 {
res = matrixMultiply(res, mat)
}
mat = matrixMultiply(mat, mat)
power /= 2
}
return res
}
func matrixMultiply(a, b [][]int) [][]int {
result := make([][]int, len(a))
for i := range result {
result[i] = make([]int, len(b[0]))
for j := range result[i] {
result[i][j] = 0
for k := range b {
result[i][j] += a[i][k] * b[k][j]
}
}
}
return result
}适用场景：
- n极大时（如n=1e6）
- 需要快速计算斐波那契数的场景
- 适合数学计算库中的算法实现
八、性能与工程实践
1. 性能优化方法
| 优化方式 | 说明 | 效果 |
|---|---|---|
| 空间优化 | 用双变量代替数组 | 空间从O(n)降至O(1) |
| 避免重复计算 | 使用记忆化缓存 | 避免递归的指数级计算 |
| 矩阵快速幂 | 将时间复杂度降至O(log n) | 适合极大n值计算 |
| 并行计算 | 使用goroutine处理独立计算任务 | 适用于多核CPU环境 |
2. 异常处理
func climbStairs(n int) int {
if n < 0 {
panic("n cannot be negative")
}
if n == 0 {
return 0
}
// ... 其他逻辑
}3. 安全风险
- 输入验证：防止恶意输入导致计算错误
- 限制计算范围：防止整数溢出
- 使用safe math库：避免溢出问题
九、常见问题与踩坑
1. 常见错误示例
// 错误：未处理n=0的情况
func climbStairs(n int) int {
if n == 1 {
return 1
}
return climbStairs(n-1) + climbStairs(n-2)
}错误原因：
- 当n=0时会进入无限递归
- 当n=2时会返回0（因为n-1=1，n-2=0）
改进方案：
func climbStairs(n int) int {
if n == 0 {
return 0
}
if n == 1 {
return 1
}
return climbStairs(n-1) + climbStairs(n-2)
}2. 其他常见问题
- 循环边界条件错误（如i < n vs i <= n）
- 数组越界访问（未初始化数组）
- 整数溢出（使用int类型时）
十、最佳实践
1. 推荐方案
- 常规场景：使用迭代法（O(n)时间，O(1)空间）
- 极大n值：使用矩阵快速幂法（O(log n)时间）
- 需要缓存中间结果：使用动态规划法
- 要求可读性：使用递归法（注意加记忆化）
2. 不推荐场景
- 需要处理大量并发请求时：避免使用递归法
- 对内存敏感的嵌入式系统：避免使用数组存储
- 需要实时计算的场景：避免使用动态规划法
十一、总结
LeetCode第70题爬楼梯作为经典的动态规划入门题，蕴含了丰富的算法思想。通过本文的深入探讨，我们了解到：
- 算法本质是斐波那契数列的变体，需要处理边界条件
- 不同实现方式有显著的性能差异，需根据实际场景选择
- 递归法虽然直观但存在严重性能问题
- 迭代法和空间优化的动态规划是工程实践中推荐的方案
- 矩阵快速幂法适合处理极大n值的计算
- 需要特别注意输入验证和异常处理
在实际项目中，当需要计算组合方案数时，可以考虑使用类似的动态规划思想。但要注意避免在需要处理大量并发请求或内存敏感的场景中使用递归或数组存储方案。通过合理选择算法实现方式，可以有效提升程序的性能和稳定性。
评论已关闭