mercerBlog

LeetCode #746 最小花费爬楼梯：动态规划经典

Fri, 05 Sep 2025 13:45:33 +0800

🧗‍♂️ 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 <= 1000
0 <= 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 数组、滚动变量），我们可以从直观到高效逐步优化。

希望这篇文章帮你彻底掌握最小花费爬楼梯问题！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！

LeetCode #509 斐波那契数

Fri, 05 Sep 2025 11:51:57 +0800

🔢 LeetCode #509 斐波那契数：动态规划入门经典

斐波那契数列是一个经典的算法问题，定义为从 0 和 1 开始，每一项是前两项之和。本文将详细解析题目，分享三种 Go 语言实现方式，帮助你从递归到动态规划逐步掌握！

📜 题目描述

来源：LeetCode #509 - Fibonacci Number

问题：
给定非负整数 n，计算斐波那契数列的第 n 项 F(n)，其中：

F(0) = 0，F(1) = 1
F(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) = 0
F(1) = 1

这个问题可以通过递归或动态规划解决。直接递归会导致重复计算，因此我们可以使用记忆化或动态规划优化性能。

💡 小贴士：斐波那契数列广泛应用于算法问题，如爬楼梯、矩阵快速幂等。

🚀 Go 语言实现

方法 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 数组、滚动变量），我们可以从直观到高效逐步优化。

希望这篇文章帮你彻底掌握斐波那契数列！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！

LeetCode #70 爬楼梯(动态规划)

Fri, 05 Sep 2025 10:44:32 +0800

🧗‍♂️ 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 数组、滚动变量），我们可以从直观到高效逐步优化。

希望这篇文章帮你彻底掌握爬楼梯问题！如果觉得有用，欢迎点赞分享 💖，也欢迎留言讨论更多算法题！