动态规划解爬楼梯问题：从斐波那契到矩阵快速幂

1. 爬楼梯问题的数学本质爬楼梯问题是一个经典的动态规划入门题目表面上看似简单实则蕴含着深刻的数学原理。假设你正在爬一个有n个台阶的楼梯每次可以跨1个或2个台阶问有多少种不同的方法可以爬到楼顶。这个问题实际上等价于斐波那契数列问题。让我们从数学角度分析当n1时只有1种方法一步登顶n2时有2种方法11或直接跨2步n3时有3种方法1111221。可以看到这正是斐波那契数列的递推关系f(n) f(n-1) f(n-2)。关键理解每个台阶的到达方式要么是从前一个台阶跨1步上来要么是从前两个台阶跨2步上来。这就是递推关系的核心逻辑。2. 递归解法及其局限性最直观的解法是使用递归def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)但这种朴素递归存在严重效率问题。以计算climbStairs(5)为例需要计算climbStairs(4)和climbStairs(3)clibStairs(4)又需要计算climbStairs(3)和climbStairs(2)可以看到climbStairs(3)被重复计算了时间复杂度达到O(2^n)当n较大时完全不可行。这就是递归解法在实际应用中最大的痛点。3. 动态规划的标准解法动态规划是解决这类问题的标准方法。我们可以使用两种实现方式3.1 自底向上的迭代法def climbStairs(n): if n 1: return 1 dp [0]*(n1) dp[1] 1 dp[2] 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这种方法创建了一个dp数组存储中间结果初始化基础情况n1和n2通过循环逐步构建更大问题的解时间复杂度O(n)空间复杂度O(n)3.2 空间优化版本观察到每个状态只依赖前两个状态可以进一步优化空间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. 矩阵快速幂解法对于追求极致效率的场景我们可以使用矩阵快速幂将时间复杂度降到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] * 2 result[0][1] * 1这种方法基于斐波那契数列的矩阵表示形式通过快速幂算法大幅提升计算效率特别适合n非常大的情况比如n10^6。5. 通用化问题扩展实际问题中楼梯问题的变种非常多常见的有5.1 可变步长版本如果每次可以跨1、2或3个台阶解法只需修改递推关系def climbStairs(n): if n 1: return 1 if n 2: return 2 if n 3: return 4 dp [0]*(n1) dp[1], dp[2], dp[3] 1, 2, 4 for i in range(4, n1): dp[i] dp[i-1] dp[i-2] dp[i-3] return dp[n]5.2 带障碍物版本LeetCode 63题就是在网格中加入障碍物def uniquePathsWithObstacles(grid): m, n len(grid), len(grid[0]) dp [[0]*n for _ in range(m)] dp[0][0] 1 if grid[0][0] 0 else 0 for i in range(1, m): dp[i][0] dp[i-1][0] if grid[i][0] 0 else 0 for j in range(1, n): dp[0][j] dp[0][j-1] if grid[0][j] 0 else 0 for i in range(1, m): for j in range(1, n): if grid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]5.3 最小代价爬楼梯LeetCode 746题要求计算最小花费def minCostClimbingStairs(cost): n len(cost) dp [0]*(n1) for i in range(2, n1): dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) return dp[n]6. 实际工程中的应用场景爬楼梯问题看似简单但其解法模式在工程中有广泛应用支付系统计算组合支付方式如用不同面额硬币支付一定金额文本处理计算字符串解码方式的数量如A1B2...Z26游戏设计角色移动路径计算金融分析计算投资组合的可能配置方式以字符串解码为例的代码实现def numDecodings(s): if not s: return 0 n len(s) dp [0]*(n1) dp[0] 1 dp[1] 0 if s[0] 0 else 1 for i in range(2, n1): if s[i-1] ! 0: dp[i] dp[i-1] two_digit int(s[i-2:i]) if 10 two_digit 26: dp[i] dp[i-2] return dp[n]7. 算法选择与性能对比不同解法在不同场景下的表现方法时间复杂度空间复杂度适用场景朴素递归O(2^n)O(n)仅适用于教学演示记忆化递归O(n)O(n)递归思路清晰但需优化动态规划O(n)O(n)标准解法易于理解空间优化DPO(n)O(1)面试最佳实践矩阵快速幂O(log n)O(1)n极大时的最优解在实际编程面试中推荐使用空间优化的动态规划解法它兼具了代码简洁性和高效性。对于特别大的n如n10^6矩阵快速幂是唯一可行的方案。8. 常见错误与调试技巧新手在解决这类问题时容易犯的错误边界条件处理不当忘记处理n0或n1的特殊情况索引越界dp数组大小设置错误递推关系错误混淆f(n-1)和f(n-2)的顺序整数溢出当n很大时结果可能超出整数范围调试建议先用小例子手工计算验证打印dp数组中间值检查是否正确添加详细的注释说明每个步骤的意图例如这是一个带有调试输出的实现def climbStairs(n): if n 1: return 1 dp [0]*(n1) dp[1] 1 dp[2] 2 print(f初始化dp[1]{dp[1]}, dp[2]{dp[2]}) for i in range(3, n1): dp[i] dp[i-1] dp[i-2] print(f计算dp[{i}]: {dp[i-1]} {dp[i-2]} {dp[i]}) return dp[n]9. 数学通项公式解法斐波那契数列其实有通项公式Binet公式f(n) (φ^n - ψ^n)/√5其中φ(1√5)/2≈1.618ψ(1-√5)/2≈-0.618Python实现def climbStairs(n): sqrt5 5**0.5 phi (1 sqrt5) / 2 psi (1 - sqrt5) / 2 return int((phi**(n1) - psi**(n1)) / sqrt5)注意由于浮点数精度问题当n较大时结果可能不准确在实际编程比赛中通常会要求对结果取模来避免大数问题10. 不同语言实现对比最后我们看看在不同编程语言中的实现差异Java实现public int climbStairs(int n) { if (n 1) return 1; int[] dp new int[n1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }C实现int climbStairs(int n) { if (n 1) return 1; vectorint dp(n1); dp[1] 1; dp[2] 2; for (int i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }JavaScript实现function climbStairs(n) { if (n 1) return 1; let dp new Array(n1); dp[1] 1; dp[2] 2; for (let i 3; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }Go实现func climbStairs(n int) int { if n 1 { return 1 } dp : make([]int, n1) dp[1] 1 dp[2] 2 for i : 3; i n; i { dp[i] dp[i-1] dp[i-2] } return dp[n] }从这些实现可以看出虽然语法不同但核心算法逻辑是完全一致的。这也体现了动态规划作为一种算法范式的通用性。