45 | 面试题：爬楼梯-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

45 | 面试题：爬楼梯

在算法面试中，“爬楼梯”问题是一道经典的动态规划（Dynamic Programming, DP）题目，它不仅考察了候选人对DP思想的理解，还测试了问题分解和状态转移的能力。这个问题通常以这样的形式出现：你正在爬楼梯，需要n步你才能到达顶端。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到顶端？

一、问题解析

首先，我们需要明确问题的输入和输出：

输入：楼梯的总级数n（n为正整数）。
输出：到达楼梯顶端的总方法数。

接下来，分析问题的基本性质：

当你站在第1级台阶时，只有1种方法到达（即直接走上去）。
当你站在第2级台阶时，有2种方法到达：一是从第1级直接跨一步上来，二是从地面直接跨两步上来。
对于第n级台阶，你可以从第n-1级跨一步上来，或者从第n-2级跨两步上来。因此，到达第n级台阶的方法数等于到达第n-1级和第n-2级的方法数之和。

这个性质揭示了问题的递归结构，即每个状态（到达某一台阶的方法数）都依赖于其前面的状态。然而，直接的递归解法会导致大量的重复计算，因此更适合采用动态规划来优化。

二、动态规划解法

动态规划通过保存已经计算过的状态来避免重复计算，从而提高效率。在本题中，我们可以使用一个数组dp来保存到达每一级台阶的方法数，其中dp[i]表示到达第i级台阶的方法数。

步骤一：初始化

dp[0] = 1（虽然实际中不存在第0级台阶，但为了方便计算，我们可以假设从“起点”（地面）到“第0级台阶”有1种方法，即不移动）。
dp[1] = 1（从地面到第1级台阶只有1种方法）。

步骤二：状态转移

对于i > 1，dp[i] = dp[i-1] + dp[i-2]（到达第i级台阶的方法数等于到达第i-1级和第i-2级的方法数之和）。

步骤三：计算并输出结果

最终，dp[n]即为所求答案，即到达第n级台阶的方法数。

三、代码实现

以下是使用Python实现的代码示例：

def climbStairs(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
# 示例
print(climbStairs(2))  # 输出: 2
print(climbStairs(3))  # 输出: 3
print(climbStairs(4))  # 输出: 5

四、优化空间复杂度

上述解法虽然简单易懂，但其空间复杂度为O(n)，因为使用了一个长度为n+1的数组来保存所有状态。考虑到状态转移方程dp[i] = dp[i-1] + dp[i-2]，我们实际上只需要知道前两个状态的值即可计算出当前状态，因此可以进一步优化空间复杂度到O(1)。

优化后的代码：

def climbStairs_optimized(n: int) -> int:
    if n <= 1:
        return n
    prev, curr = 1, 1
    for i in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr
# 示例
print(climbStairs_optimized(2))  # 输出: 2
print(climbStairs_optimized(3))  # 输出: 3
print(climbStairs_optimized(4))  # 输出: 5

五、问题扩展

“爬楼梯”问题还可以进一步扩展，以增加其难度和考察的广度。例如：

每次可以爬的台阶数不限于1或2，而是给定一个数组，数组中的每个元素代表一个你可以爬的台阶数。
带有惩罚的爬楼梯，比如每爬2个台阶就会消耗一定的体力值，体力值耗尽则无法继续爬楼，问最多能爬到第几级台阶。
带权重的爬楼梯，即每爬一级台阶都有不同的收益，求最大收益下的爬楼梯方法数。

这些问题都需要在基本DP框架上进行适当的修改和扩展，以应对新的约束条件和目标。

六、总结

“爬楼梯”问题作为动态规划的经典题目，不仅考察了算法基础知识的掌握情况，还培养了问题分解和状态转移的能力。通过这个问题，我们可以深入理解动态规划的思想，并学会如何将其应用到实际问题的解决中。此外，通过问题的扩展，我们还可以进一步锻炼自己的思维能力和算法设计能力。