LeetCode 70. Climbing Stairs 爬楼梯动态规划与斐波那契数列的 Go 实现解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 70 题「爬楼梯」Climbing Stairs展开完整讲解题目的递推建模、状态转移方程并结合开源仓库 LeetCode-Go 中 leetcode/0070.Climbing-Stairs/70. Climbing Stairs.go 的源码逐行剖析其动态规划实现。读完本文你将掌握爬楼梯问题的经典 DP 解法、复杂度分析与空间优化思路并能通过仓库自带的测试用例验证实现正确性同时理解该题与斐波那契数列的深层联系。题目描述You are climbing a stair case. It takesnsteps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note:Givennwill be a positive integer.Example 1:Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step 1 step 2. 2 stepsExample 2:Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step 1 step 1 step 2. 1 step 2 steps 3. 2 steps 1 step题目大意假设你正在爬楼梯需要 n 阶才能到达楼顶。每次你可以爬 1 个或 2 个台阶问有多少种不同的方法可以爬到楼顶。注意给定的 n 是一个正整数。解题思路递推关系与状态定义原文档给出的核心思路非常凝练值得展开这是一个简单的 DP经典的爬楼梯问题。一个楼梯可以由n-1和n-2的楼梯爬上来。设dp[i]表示爬到第i阶台阶的不同方法总数那么要到达第i阶最后一步只可能来自第i-1阶走 1 步或第i-2阶走 2 步由于两种到达方式互斥且覆盖全部情况总方案数为二者之和。由此得到状态转移方程dp[i] dp[i-1] dp[i-2]边界条件为dp[0] 1站在地面可视为 1 种“空方案”便于统一递推与dp[1] 1只有一步直接跨上。该递推关系恰好就是斐波那契数列的形式因此这一题求解的值就是斐波那契数列——这也是原文档解题思路中的核心结论。仓库源码实现精读仓库中 leetcode/0070.Climbing-Stairs/70. Climbing Stairs.go 给出了完整实现package leetcode func climbStairs(n int) int { dp : make([]int, n1) dp[0], dp[1] 1, 1 for i : 2; i n; i { dp[i] dp[i-1] dp[i-2] } return dp[n] }逐行分析如下dp : make([]int, n1)申请长度为n1的切片下标0..n对应地面到第 n 阶避免数组越界与额外的下标换算dp[0], dp[1] 1, 1初始化两个边界。dp[1] 1是题目直接可验证的1 阶只有 1 种走法dp[0] 1则保证i 2时dp[2] dp[1] dp[0] 2与示例 1 吻合循环体dp[i] dp[i-1] dp[i-2]自底向上bottom-up迭代计算严格对应状态转移方程每个状态只依赖前两个状态无重复计算return dp[n]直接返回第 n 阶的方法总数。由于题目保证n为正整数dp切片的最小长度恒为 2无需额外处理n 0的空输入场景。复杂度分析从源码结构可以直观推断时间复杂度O(n)。循环从 2 迭代到 n共n-1次加法运算空间复杂度O(n)。使用了一个长度为n1的 DP 数组。与递归写法相比该实现避免了指数级的重复子问题计算与备忘录递归相比又省去了函数调用栈开销是典型的自底向上动态规划。空间优化从 O(n) 到 O(1)观察递推式dp[i] dp[i-1] dp[i-2]可以发现计算第 i 个状态时只用到前两个状态更早的dp[0..i-3]不再参与后续计算。因此可以使用两个滚动变量替代整个数组把空间复杂度降到 O(1)。下面是一种常见的优化写法不属于本仓库已提交内容仅作扩展参考func climbStairsOptimized(n int) int { if n 1 { return 1 } prev2, prev1 : 1, 1 // dp[0], dp[1] for i : 2; i n; i { prev2, prev1 prev1, prev1prev2 } return prev1 }优化后仍保持 O(n) 时间但空间占用与 n 无关这在 n 极大时尤为重要。与斐波那契数列的关系原文档明确指出“这一题求解的值就是斐波那契数列”。具体地若定义标准斐波那契数列F(0) 0, F(1) 1则爬楼梯答案满足dp[n] F(n1)。以 n 5 为例dp: 1, 1, 2, 3, 5, 8 F: 0, 1, 1, 2, 3, 5dp[5] 8 F(6)对应关系完全一致。仓库中另有同族题目可供对照练习leetcode/0509.Fibonacci-Number/README.md直接求解斐波那契数列可对比其递推实现leetcode/1137.N-th-Tribonacci-Number/README.md把“一次走 1 或 2 步”扩展为“三个前驱状态求和”的泰波那契数列递推模式一脉相承。测试用例验证仓库为本题提供了单元测试文件 leetcode/0070.Climbing-Stairs/70. Climbing Stairs_test.go覆盖了题目给出的两个官方示例qs : []question70{ { para70{2}, ans70{2}, }, { para70{3}, ans70{3}, }, }测试运行时对每个用例调用climbStairs(p.n)并打印输入输出对照。在本目录执行测试的命令为go test ./leetcode/0070.Climbing-Stairs/若想运行仓库全部题解测试并生成覆盖率文件可使用仓库根目录提供的 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本一次对所有 leetcode 子包执行测试并产出单一、合法的 Go 覆盖率文件 coverage.txt与仓库“100% test coverage”的目标一致。小结爬楼梯是动态规划入门最经典的题目之一从“最后一步怎么走”入手建立递推关系自底向上迭代求解最后还能通过滚动变量把空间优化到常数级。掌握本题的建模方式后无论是斐波那契数列、泰波那契数列还是更复杂的路径计数类 DP如二维网格路径问题都能复用同一套“定义状态 → 推导转移方程 → 边界初始化 → 迭代求解”的方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 70. Climbing Stairs 爬楼梯：动态规划与斐波那契数列的 Go 实现解析
LeetCode 70. Climbing Stairs 爬楼梯动态规划与斐波那契数列的 Go 实现解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 70 题「爬楼梯」Climbing Stairs展开完整讲解题目的递推建模、状态转移方程并结合开源仓库 LeetCode-Go 中 leetcode/0070.Climbing-Stairs/70. Climbing Stairs.go 的源码逐行剖析其动态规划实现。读完本文你将掌握爬楼梯问题的经典 DP 解法、复杂度分析与空间优化思路并能通过仓库自带的测试用例验证实现正确性同时理解该题与斐波那契数列的深层联系。题目描述You are climbing a stair case. It takesnsteps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note:Givennwill be a positive integer.Example 1:Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step 1 step 2. 2 stepsExample 2:Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step 1 step 1 step 2. 1 step 2 steps 3. 2 steps 1 step题目大意假设你正在爬楼梯需要 n 阶才能到达楼顶。每次你可以爬 1 个或 2 个台阶问有多少种不同的方法可以爬到楼顶。注意给定的 n 是一个正整数。解题思路递推关系与状态定义原文档给出的核心思路非常凝练值得展开这是一个简单的 DP经典的爬楼梯问题。一个楼梯可以由n-1和n-2的楼梯爬上来。设dp[i]表示爬到第i阶台阶的不同方法总数那么要到达第i阶最后一步只可能来自第i-1阶走 1 步或第i-2阶走 2 步由于两种到达方式互斥且覆盖全部情况总方案数为二者之和。由此得到状态转移方程dp[i] dp[i-1] dp[i-2]边界条件为dp[0] 1站在地面可视为 1 种“空方案”便于统一递推与dp[1] 1只有一步直接跨上。该递推关系恰好就是斐波那契数列的形式因此这一题求解的值就是斐波那契数列——这也是原文档解题思路中的核心结论。仓库源码实现精读仓库中 leetcode/0070.Climbing-Stairs/70. Climbing Stairs.go 给出了完整实现package leetcode func climbStairs(n int) int { dp : make([]int, n1) dp[0], dp[1] 1, 1 for i : 2; i n; i { dp[i] dp[i-1] dp[i-2] } return dp[n] }逐行分析如下dp : make([]int, n1)申请长度为n1的切片下标0..n对应地面到第 n 阶避免数组越界与额外的下标换算dp[0], dp[1] 1, 1初始化两个边界。dp[1] 1是题目直接可验证的1 阶只有 1 种走法dp[0] 1则保证i 2时dp[2] dp[1] dp[0] 2与示例 1 吻合循环体dp[i] dp[i-1] dp[i-2]自底向上bottom-up迭代计算严格对应状态转移方程每个状态只依赖前两个状态无重复计算return dp[n]直接返回第 n 阶的方法总数。由于题目保证n为正整数dp切片的最小长度恒为 2无需额外处理n 0的空输入场景。复杂度分析从源码结构可以直观推断时间复杂度O(n)。循环从 2 迭代到 n共n-1次加法运算空间复杂度O(n)。使用了一个长度为n1的 DP 数组。与递归写法相比该实现避免了指数级的重复子问题计算与备忘录递归相比又省去了函数调用栈开销是典型的自底向上动态规划。空间优化从 O(n) 到 O(1)观察递推式dp[i] dp[i-1] dp[i-2]可以发现计算第 i 个状态时只用到前两个状态更早的dp[0..i-3]不再参与后续计算。因此可以使用两个滚动变量替代整个数组把空间复杂度降到 O(1)。下面是一种常见的优化写法不属于本仓库已提交内容仅作扩展参考func climbStairsOptimized(n int) int { if n 1 { return 1 } prev2, prev1 : 1, 1 // dp[0], dp[1] for i : 2; i n; i { prev2, prev1 prev1, prev1prev2 } return prev1 }优化后仍保持 O(n) 时间但空间占用与 n 无关这在 n 极大时尤为重要。与斐波那契数列的关系原文档明确指出“这一题求解的值就是斐波那契数列”。具体地若定义标准斐波那契数列F(0) 0, F(1) 1则爬楼梯答案满足dp[n] F(n1)。以 n 5 为例dp: 1, 1, 2, 3, 5, 8 F: 0, 1, 1, 2, 3, 5dp[5] 8 F(6)对应关系完全一致。仓库中另有同族题目可供对照练习leetcode/0509.Fibonacci-Number/README.md直接求解斐波那契数列可对比其递推实现leetcode/1137.N-th-Tribonacci-Number/README.md把“一次走 1 或 2 步”扩展为“三个前驱状态求和”的泰波那契数列递推模式一脉相承。测试用例验证仓库为本题提供了单元测试文件 leetcode/0070.Climbing-Stairs/70. Climbing Stairs_test.go覆盖了题目给出的两个官方示例qs : []question70{ { para70{2}, ans70{2}, }, { para70{3}, ans70{3}, }, }测试运行时对每个用例调用climbStairs(p.n)并打印输入输出对照。在本目录执行测试的命令为go test ./leetcode/0070.Climbing-Stairs/若想运行仓库全部题解测试并生成覆盖率文件可使用仓库根目录提供的 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本一次对所有 leetcode 子包执行测试并产出单一、合法的 Go 覆盖率文件 coverage.txt与仓库“100% test coverage”的目标一致。小结爬楼梯是动态规划入门最经典的题目之一从“最后一步怎么走”入手建立递推关系自底向上迭代求解最后还能通过滚动变量把空间优化到常数级。掌握本题的建模方式后无论是斐波那契数列、泰波那契数列还是更复杂的路径计数类 DP如二维网格路径问题都能复用同一套“定义状态 → 推导转移方程 → 边界初始化 → 迭代求解”的方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考