LeetCode #746 最小花费爬楼梯：动态规划经典
🧗♂️ LeetCode #746 最小花费爬楼梯：动态规划经典
给定一个整数数组 cost，其中 cost[i] 表示从第 i 个台阶向上爬需要支付的费用。支付费用后，你可以选择爬 1 或 2 个台阶。你可以从下标 0 或 1 开始，目标是到达楼梯顶部（超出数组的最后一步）。请计算到达楼梯顶部的最低花费。
本文将详细解析题目，提供三种 Go 语言实现方式，帮助你从递归到动态规划逐步掌握！
📜 题目描述
来源：LeetCode #746 - Min Cost Climbing Stairs
问题：
给定整数数组 cost，cost[i] 是从第 i 个台阶向上爬的费用。支付费用后，可选择爬 1 或 2 个台阶。你可以从下标 0 或 1 开始，计算到达楼梯顶部（第 n 步）的最低花费。
示例 1
输入：cost = [10,15,20]
输出：15
解释：
从下标 1 开始：
支付 15，爬 2 个台阶到达顶部。
总花费为 15。
示例 2
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：
从下标 0 开始：
支付 1，爬 2 阶到下标 2。
支付 1，爬 2 阶到下标 4。
支付 1，爬 2 阶到下标 6。
支付 1，爬 1 阶到下标 7。
支付 1，爬 2 阶到下标 9。
支付 1，爬 1 阶到顶部。
总花费为 6。
约束
2 <= cost.length <= 10000 <= cost[i] <= 999
💡 解题思路
核心观察
要到达楼梯顶部（第 n 步），你必须从第 n-1 或 n-2 个台阶爬上来。因此，到达第 i 个台阶的最低花费可以表示为：
从
i-1爬 1 步：需支付cost[i-1]加上到达i-1的最低花费。从
i-2爬 2 步：需支付cost[i-2]加上到达i-2的最低花费。
状态转移方程：
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
初始条件：
dp[0] = 0（从下标 0 开始，初始花费为 0）dp[1] = 0（从下标 1 开始，初始花费为 0）
💡 小贴士：楼梯顶部是第
n步，需计算dp[n]。本题与爬楼梯问题类似，但增加了费用优化。
🚀 Go 语言实现
以下是三种 Go 语言实现方式，从递归到动态规划逐步优化，适合不同场景。代码块使用 go 语法高亮，建议在富文本编辑器中启用深色主题（如 monokai 或 dracula）以增强可读性。
方法 1：递归 + 记忆化
通过递归解决，使用记忆化数组避免重复计算。
package main
import "fmt"
func minCostClimbingStairs(cost []int) int {
n := len(cost)
memo := make([]int, n+1)
return dfs(n, cost, memo)
}
func dfs(i int, cost, memo []int) int {
if i <= 1 {
return 0
}
if memo[i] != 0 {
return memo[i]
}
memo[i] = min(dfs(i-1, cost, memo)+cost[i-1], dfs(i-2, cost, memo)+cost[i-2])
return memo[i]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
fmt.Println(minCostClimbingStairs([]int{10, 15, 20})) // 输出: 15
fmt.Println(minCostClimbingStairs([]int{1, 100, 1, 1, 1, 100, 1, 1, 100, 1})) // 输出: 6
}时间复杂度：O(n)
空间复杂度：O(n)
优点：直观，体现递归思想
缺点：需要额外内存存储记忆化数组
方法 2：动态规划（DP 数组）
使用数组存储每个台阶的最低花费，迭代计算。
package main
import "fmt"
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
dp[0], dp[1] = 0, 0
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
fmt.Println(minCostClimbingStairs([]int{10, 15, 20})) // 输出: 15
fmt.Println(minCostClimbingStairs([]int{1, 100, 1, 1, 1, 100, 1, 1, 100, 1})) // 输出: 6
}时间复杂度：O(n)
空间复杂度：O(n)
优点：逻辑清晰，适合初学者理解动态规划
缺点：空间占用较多
方法 3：空间优化（滚动变量）🔥
仅用两个变量存储前两步的最低花费，优化空间复杂度。
package main
import "fmt"
func minCostClimbingStairs(cost []int) int {
n := len(cost)
prev, curr := 0, 0
for i := 2; i <= n; i++ {
next := min(curr+cost[i-1], prev+cost[i-2])
prev = curr
curr = next
}
return curr
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
fmt.Println(minCostClimbingStairs([]int{10, 15, 20})) // 输出: 15
fmt.Println(minCostClimbingStairs([]int{1, 100, 1, 1, 1, 100, 1, 1, 100, 1})) // 输出: 6
}时间复杂度：O(n)
空间复杂度：O(1)
优点：高效简洁，面试最佳写法
推荐指数：⭐⭐⭐⭐⭐
📊 方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 推荐指数 |
|---|---|---|---|
| 递归 + 记忆化 | O(n) | O(n) | ⭐⭐⭐☆ |
| DP 数组 | O(n) | O(n) | ⭐⭐⭐⭐ |
| 滚动变量（最优） | O(n) | O(1) | ⭐⭐⭐⭐⭐ |
注意：由于
cost[i] <= 999且cost.length <= 1000，结果不会溢出 Go 的int类型。
🎯 进阶思考
扩展步长：如果可以爬 1、2 或 3 个台阶？
状态转移方程需考虑更多前驱状态：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2], dp[i-3] + cost[i-3])。动态费用：如果费用随时间变化？
需引入时间维度，调整 DP 模型。更高效率：能否用其他优化方法？
对于特定输入，可能通过数学规律或预处理进一步优化。
💡 学习建议：
初学者：从递归和 DP 数组入手，理解状态转移。
进阶者：掌握滚动变量优化，体会空间优化的精髓。
高手：探索扩展问题，尝试更复杂的动态规划场景。
🔚 总结
“最小花费爬楼梯”问题是动态规划的经典变种，核心在于状态转移方程 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。通过三种 Go 实现（递归、DP 数组、滚动变量），我们可以从直观到高效逐步优化。
希望这篇文章帮你彻底掌握最小花费爬楼梯问题！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！