LeetCode/LintCode 题解丨美团面试题：爬楼梯
2026-02-21 19:04:21
爬楼梯问题是一个经典的动态规划问题，其核心在于找到到达第n阶楼梯的方法数。
问题分析：
每次只能爬1步或2步，因此到达第n阶楼梯的方法数等于到达第n-1阶楼梯的方法数加上到达第n-2阶楼梯的方法数。
这是一个典型的斐波那契数列问题，其中f(n) = f(n-1) + f(n-2)。
动态规划解法：
初始化：当n为0或1时，只有1种方法（即不爬或爬1步）。
迭代计算：从2到n，使用两个变量last和lastlast分别记录前两个台阶的方法数，通过迭代更新当前台阶的方法数now。
时间复杂度：O(n)，因为需要遍历从2到n的所有台阶。
空间复杂度：O(1)，仅使用了常数个额外空间。
记忆化搜索解法：
初始化：创建一个数组result来存储每个台阶的方法数，初始时所有值设为-1表示未计算。
递归计算：定义一个递归函数f(X)，如果result[X]已经计算过（不为-1），则直接返回；否则，递归计算f(X-1)和f(X-2)，并将结果存储在result[X]中。
时间复杂度：O(n)，每个台阶的方法数只计算一次。
空间复杂度：O(n)，用于存储result数组。
代码实现：
动态规划解法通过迭代高效地计算出结果，适合大规模数据。
记忆化搜索解法通过递归和记忆化技术避免了重复计算，但递归调用可能带来额外的栈空间开销。
示例与验证：
对于样例输入（如n=3），动态规划解法会计算出now为3（1+1+1, 1+2, 2+1），与预期结果一致。
记忆化搜索解法同样能正确计算出结果，但需要通过递归调用填充result数组。
优化与扩展：
可以进一步优化空间复杂度，例如使用矩阵快速幂或通项公式（斐波那契数列的通项公式）来计算，但这些方法可能增加实现的复杂性。
对于更大的n值，可以考虑使用大整数类来避免整数溢出问题。
通过动态规划和记忆化搜索两种方法，可以有效地解决爬楼梯问题。动态规划方法更为直观且空间效率高，而记忆化搜索方法则展示了递归和记忆化技术的结合应用。
热门标签
