1. 问题背景与题目解析爬楼梯是力扣LeetCode平台上经典的动态规划入门题目编号为第70题而非81题可能是用户输入有误。这道题之所以被广泛讨论是因为它完美展现了动态规划的核心思想——将复杂问题分解为简单子问题并通过存储子问题的解来避免重复计算。题目描述很简单假设你正在爬楼梯每次你可以跨1个台阶或2个台阶。问到达第n个台阶有多少种不同的方法。例如n1时只有1种方法1步n2时有2种方法11或直接2步n3时有3种方法1111221这个问题看似简单但蕴含着计算机科学中非常重要的算法思想。我在第一次遇到这个问题时也曾陷入暴力递归的陷阱直到理解了动态规划的精妙之处。2. 暴力递归解法及其缺陷最直观的解法是递归要到达第n阶可以从n-1阶跨1步或从n-2阶跨2步。因此方法总数就是这两种情况之和。def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)这个解法虽然正确但存在严重的性能问题。以n5为例调用树如下climbStairs(5) ├── climbStairs(4) │ ├── climbStairs(3) │ │ ├── climbStairs(2) │ │ └── climbStairs(1) │ └── climbStairs(2) └── climbStairs(3) ├── climbStairs(2) └── climbStairs(1)可以看到climbStairs(3)被计算了两次climbStairs(2)被计算了三次。时间复杂度是O(2^n)当n40时普通计算机需要几分钟才能算出结果。提示这是递归解法常见的重复子问题现象也是动态规划要解决的核心问题。3. 动态规划解法详解动态规划通过存储子问题的解来避免重复计算。对于爬楼梯问题我们可以使用两种实现方式3.1 自顶向下的记忆化递归在递归基础上增加一个备忘录存储已计算结果def climbStairs(n, memo{}): if n in memo: return memo[n] if n 1: return 1 if n 2: return 2 memo[n] climbStairs(n-1, memo) climbStairs(n-2, memo) return memo[n]这种方法的时间复杂度降为O(n)因为每个子问题只计算一次。空间复杂度也是O(n)用于存储备忘录。3.2 自底向上的迭代法更常见的动态规划实现方式是使用数组迭代def climbStairs(n): if n 1: return 1 dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种方法同样具有O(n)时间复杂度和O(n)空间复杂度但避免了递归带来的函数调用开销。3.3 空间优化版本观察发现当前状态只依赖前两个状态因此可以进一步优化空间def climbStairs(n): if n 1: return 1 first, second 1, 2 for _ in range(3, n1): first, second second, first second return second这样空间复杂度降为O(1)是这个问题的最优解法。4. 数学视角斐波那契数列有趣的是爬楼梯问题的解序列正是著名的斐波那契数列偏移一位。斐波那契数列定义 F(1)1, F(2)1, F(n)F(n-1)F(n-2) (n2)而爬楼梯问题的解 S(1)1F(2), S(2)2F(3), S(3)3F(4),...因此有S(n)F(n1)。这个关联让我们可以利用斐波那契数列的数学性质来解决问题。4.1 通项公式法斐波那契数列有通项公式Binet公式 F(n) (φ^n - ψ^n)/√5 其中φ(1√5)/2≈1.618黄金比例ψ(1-√5)/2≈-0.618因此可以推导出def climbStairs(n): sqrt5 5**0.5 phi (1 sqrt5) / 2 return int((phi**(n1) - (-phi)**(-n-1)) / sqrt5)这种方法的时间复杂度是O(1)但需要注意浮点数精度问题当n较大时可能产生误差。4.2 矩阵快速幂利用矩阵乘法可以高效计算斐波那契数[F(n) ] [1 1] [F(n-1)] [F(n-1)] [1 0] [F(n-2)]通过矩阵快速幂可以在O(log n)时间内求解def climbStairs(n): def matrix_pow(mat, power): result [[1,0],[0,1]] # 单位矩阵 while power 0: if power % 2 1: result matrix_mult(result, mat) mat matrix_mult(mat, mat) power // 2 return result def matrix_mult(a, b): return [ [a[0][0]*b[0][0] a[0][1]*b[1][0], a[0][0]*b[0][1] a[0][1]*b[1][1]], [a[1][0]*b[0][0] a[1][1]*b[1][0], a[1][0]*b[0][1] a[1][1]*b[1][1]] ] if n 1: return 1 mat [[1,1],[1,0]] result matrix_pow(mat, n-1) return result[0][0] result[0][1]这种方法虽然理论复杂度最优但实现较复杂在面试中通常不需要展示。5. 变种问题与实际应用掌握了基础解法后我们可以探讨一些变种问题这些在面试中也经常出现5.1 每次可以爬1、2或3个台阶此时递推关系变为S(n) S(n-1) S(n-2) S(n-3) 初始条件S(0)1, S(1)1, S(2)2解法只需稍作修改def climbStairs(n): if n 0: return 1 if n 1: return 1 if n 2: return 2 first, second, third 1, 1, 2 for _ in range(3, n1): first, second, third second, third, first second third return third5.2 有体力消耗限制假设每次爬楼梯有体力消耗求消耗最少的路径。这就变成了典型的动态规划问题需要记录到达每阶的最小消耗。5.3 实际应用场景爬楼梯问题看似简单但其思想广泛应用于金融领域的投资组合优化生物信息学的序列比对计算机图形学的路径规划网络路由算法6. 面试中的注意事项在技术面试中遇到这个问题时建议按照以下步骤展开先确认题目要求如n的范围、是否可以跨3步等提出暴力递归解法并分析复杂度指出重复计算问题引入记忆化递归转换为自底向上的动态规划进行空间优化讨论可能的变种和边界条件注意面试官通常会追问如果每次可以跨m步怎么办或如果某些台阶不能踩怎么办等问题要准备好这些变种的思路。7. 个人实战经验分享在刷题过程中我发现这类问题有几个常见陷阱边界条件容易忽略n0时应该返回1表示地面有1种方法但很多解法会出错空间优化时变量更新顺序很重要错误的顺序会导致计算结果错误Python中递归深度限制默认1000对于大n会栈溢出一个实用的调试技巧是先用小例子n1到5手动计算验证代码输出是否正确。对于优化后的版本可以打印中间变量来确认计算过程。最后这道题的价值不仅在于解法本身更在于理解动态规划的思想。掌握这个思想后很多更复杂的问题都能迎刃而解。
1. 问题背景与题目解析爬楼梯是力扣LeetCode平台上经典的动态规划入门题目编号为第70题而非81题可能是用户输入有误。这道题之所以被广泛讨论是因为它完美展现了动态规划的核心思想——将复杂问题分解为简单子问题并通过存储子问题的解来避免重复计算。题目描述很简单假设你正在爬楼梯每次你可以跨1个台阶或2个台阶。问到达第n个台阶有多少种不同的方法。例如n1时只有1种方法1步n2时有2种方法11或直接2步n3时有3种方法1111221这个问题看似简单但蕴含着计算机科学中非常重要的算法思想。我在第一次遇到这个问题时也曾陷入暴力递归的陷阱直到理解了动态规划的精妙之处。2. 暴力递归解法及其缺陷最直观的解法是递归要到达第n阶可以从n-1阶跨1步或从n-2阶跨2步。因此方法总数就是这两种情况之和。def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)这个解法虽然正确但存在严重的性能问题。以n5为例调用树如下climbStairs(5) ├── climbStairs(4) │ ├── climbStairs(3) │ │ ├── climbStairs(2) │ │ └── climbStairs(1) │ └── climbStairs(2) └── climbStairs(3) ├── climbStairs(2) └── climbStairs(1)可以看到climbStairs(3)被计算了两次climbStairs(2)被计算了三次。时间复杂度是O(2^n)当n40时普通计算机需要几分钟才能算出结果。提示这是递归解法常见的重复子问题现象也是动态规划要解决的核心问题。3. 动态规划解法详解动态规划通过存储子问题的解来避免重复计算。对于爬楼梯问题我们可以使用两种实现方式3.1 自顶向下的记忆化递归在递归基础上增加一个备忘录存储已计算结果def climbStairs(n, memo{}): if n in memo: return memo[n] if n 1: return 1 if n 2: return 2 memo[n] climbStairs(n-1, memo) climbStairs(n-2, memo) return memo[n]这种方法的时间复杂度降为O(n)因为每个子问题只计算一次。空间复杂度也是O(n)用于存储备忘录。3.2 自底向上的迭代法更常见的动态规划实现方式是使用数组迭代def climbStairs(n): if n 1: return 1 dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种方法同样具有O(n)时间复杂度和O(n)空间复杂度但避免了递归带来的函数调用开销。3.3 空间优化版本观察发现当前状态只依赖前两个状态因此可以进一步优化空间def climbStairs(n): if n 1: return 1 first, second 1, 2 for _ in range(3, n1): first, second second, first second return second这样空间复杂度降为O(1)是这个问题的最优解法。4. 数学视角斐波那契数列有趣的是爬楼梯问题的解序列正是著名的斐波那契数列偏移一位。斐波那契数列定义 F(1)1, F(2)1, F(n)F(n-1)F(n-2) (n2)而爬楼梯问题的解 S(1)1F(2), S(2)2F(3), S(3)3F(4),...因此有S(n)F(n1)。这个关联让我们可以利用斐波那契数列的数学性质来解决问题。4.1 通项公式法斐波那契数列有通项公式Binet公式 F(n) (φ^n - ψ^n)/√5 其中φ(1√5)/2≈1.618黄金比例ψ(1-√5)/2≈-0.618因此可以推导出def climbStairs(n): sqrt5 5**0.5 phi (1 sqrt5) / 2 return int((phi**(n1) - (-phi)**(-n-1)) / sqrt5)这种方法的时间复杂度是O(1)但需要注意浮点数精度问题当n较大时可能产生误差。4.2 矩阵快速幂利用矩阵乘法可以高效计算斐波那契数[F(n) ] [1 1] [F(n-1)] [F(n-1)] [1 0] [F(n-2)]通过矩阵快速幂可以在O(log n)时间内求解def climbStairs(n): def matrix_pow(mat, power): result [[1,0],[0,1]] # 单位矩阵 while power 0: if power % 2 1: result matrix_mult(result, mat) mat matrix_mult(mat, mat) power // 2 return result def matrix_mult(a, b): return [ [a[0][0]*b[0][0] a[0][1]*b[1][0], a[0][0]*b[0][1] a[0][1]*b[1][1]], [a[1][0]*b[0][0] a[1][1]*b[1][0], a[1][0]*b[0][1] a[1][1]*b[1][1]] ] if n 1: return 1 mat [[1,1],[1,0]] result matrix_pow(mat, n-1) return result[0][0] result[0][1]这种方法虽然理论复杂度最优但实现较复杂在面试中通常不需要展示。5. 变种问题与实际应用掌握了基础解法后我们可以探讨一些变种问题这些在面试中也经常出现5.1 每次可以爬1、2或3个台阶此时递推关系变为S(n) S(n-1) S(n-2) S(n-3) 初始条件S(0)1, S(1)1, S(2)2解法只需稍作修改def climbStairs(n): if n 0: return 1 if n 1: return 1 if n 2: return 2 first, second, third 1, 1, 2 for _ in range(3, n1): first, second, third second, third, first second third return third5.2 有体力消耗限制假设每次爬楼梯有体力消耗求消耗最少的路径。这就变成了典型的动态规划问题需要记录到达每阶的最小消耗。5.3 实际应用场景爬楼梯问题看似简单但其思想广泛应用于金融领域的投资组合优化生物信息学的序列比对计算机图形学的路径规划网络路由算法6. 面试中的注意事项在技术面试中遇到这个问题时建议按照以下步骤展开先确认题目要求如n的范围、是否可以跨3步等提出暴力递归解法并分析复杂度指出重复计算问题引入记忆化递归转换为自底向上的动态规划进行空间优化讨论可能的变种和边界条件注意面试官通常会追问如果每次可以跨m步怎么办或如果某些台阶不能踩怎么办等问题要准备好这些变种的思路。7. 个人实战经验分享在刷题过程中我发现这类问题有几个常见陷阱边界条件容易忽略n0时应该返回1表示地面有1种方法但很多解法会出错空间优化时变量更新顺序很重要错误的顺序会导致计算结果错误Python中递归深度限制默认1000对于大n会栈溢出一个实用的调试技巧是先用小例子n1到5手动计算验证代码输出是否正确。对于优化后的版本可以打印中间变量来确认计算过程。最后这道题的价值不仅在于解法本身更在于理解动态规划的思想。掌握这个思想后很多更复杂的问题都能迎刃而解。
