1. 项目概述:楼梯问题的数学本质
"P1255 数楼梯"这道题目看似简单,却蕴含着丰富的数学思维和算法思想。题目要求计算到达第n级楼梯的不同方法数,每次可以跨1级或2级。这实际上就是著名的斐波那契数列问题,在力扣等编程题库中被归类为动态规划的入门经典。
我第一次接触这个问题时,以为只是简单的排列组合,但深入思考后发现其中蕴含着递归、动态规划、矩阵快速幂等多种解法。这个问题之所以被广泛用作算法教学的案例,正是因为它能很好地展示算法思维从简单到复杂的演进过程。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 核心解法解析
2.1 递归解法:最直观的思路
最直接的思路是递归:到达第n级楼梯的方法数等于到达第(n-1)级和(n-2)级方法数之和。这是因为最后一步要么跨1级,要么跨2级。
python复制def climbStairs(n):
if n <= 2:
return n
return climbStairs(n-1) + climbStairs(n-2)
注意:这种解法虽然简洁,但时间复杂度是O(2^n),当n较大时会出现严重的性能问题。我在本地测试时,n=40就已经需要数秒才能计算出结果。
2.2 动态规划:优化递归的重复计算
递归解法的主要问题是重复计算。动态规划通过存储中间结果来避免这种浪费:
python复制def climbStairs(n):
if n <= 2:
return n
dp = [0]*(n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
这个版本的时间复杂度降到了O(n),空间复杂度也是O(n)。在实际编码比赛中,这是最常用的解法之一。
2.3 空间优化的动态规划
进一步观察可以发现,我们只需要保存前两个状态:
python复制def climbStairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n+1):
a, b = b, a+b
