从LeetCode 70题“爬楼梯”出发，聊聊面试官最爱问的四种解法（附Python/Java代码）

算法面试中，经典题目"爬楼梯"就像一面镜子，能清晰照出候选人的解题思维层次。这道看似简单的题目背后，藏着递归优化、动态规划进阶等多个考察维度。本文将从面试官评分视角，拆解四种解法的得分要点，并对比Python与Java的实现差异。

1. 递归解法：思维直白但暗藏陷阱

递归是大多数人面对这道题的第一反应。当面试官听到"可以用递归解决"时，他们期待的是候选人能立即意识到潜在的性能问题。

核心递推公式 ： f(n) = f(n-1) + f(n-2)
边界条件 ： f(1)=1 , f(2)=2

Python实现：

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    return climbStairs(n-1) + climbStairs(n-2)

Java实现：

public int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n-1) + climbStairs(n-2);
}

面试官考察重点 ：

• 能否准确分析时间复杂度（O(2^n)）
• 是否发现重复计算问题
• 对递归深度的敏感度（n=45时栈溢出风险）

提示：当候选人给出递归解法时，面试官通常会追问"这个解法有什么问题？"，此时应主动指出重复计算缺陷。

2. 记忆化递归：展示优化思维的关键转折

记忆化（Memoization）是递归解法的自然进化，也是面试中的加分项。优秀的候选人会主动提出："我们可以用缓存来避免重复计算"。

Python实现（使用装饰器）：

from functools import lru_cache

@lru_cache(maxsize=None)
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    return climbStairs(n-1) + climbStairs(n-2)

Java实现（手动缓存）：

class Solution {
    private int[] memo = new int[46];
    
    public int climbStairs(int n) {
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = climbStairs(n-1) + climbStairs(n-2);
        return memo[n];
    }
}

性能对比 ：

指标	普通递归	记忆化递归
时间复杂度	O(2^n)	O(n)
空间复杂度	O(n)	O(n)
最大可计算n	~30	45

面试话术模板 ： "我注意到递归解法存在重复计算问题，可以通过引入缓存来优化。这里Python可以用 lru_cache 装饰器自动实现，Java则需要手动维护记忆数组..."

3. 动态规划：面试中的标准答案

动态规划(DP)解法是面试官最期待的解决方案。候选人需要展示从递归→记忆化→DP的完整思维链条。

Python实现：

def climbStairs(n: int) -> int:
    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]

Java实现：

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n+1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

面试得分点 ：

1. 状态定义清晰（dp[i]表示i阶楼梯的方法数）
2. 正确初始化边界条件
3. 递推公式准确
4. 空间复杂度分析（可优化为O(1)）

注意：有经验的面试官会要求在不使用数组的情况下实现DP，这就引出了最终的优化方案——滚动数组。

4. 滚动数组：空间优化的终极形态

当候选人给出DP解法后，面试官常会追问："能否进一步优化空间复杂度？"这时滚动数组解法就能展现候选人的深度优化能力。

Python实现：

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a+b
    return b

Java实现：

public int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

优化原理 ：

• 只维护前两个状态值（a和b）
• 通过变量滚动更新代替数组存储
• 空间复杂度从O(n)降为O(1)

面试应答策略 ： "考虑到每个状态只依赖前两个状态，我们可以用两个变量交替存储，这样既保留了DP的优点，又减少了空间消耗。这种方法在处理斐波那契类问题时非常有效..."

5. 语言特性对比与面试实战技巧

不同语言的实现细节会影响面试表现。以下是Python和Java的关键差异点：

语法对比表 ：

特性	Python	Java
默认参数检查	动态类型无需声明	需显式声明参数和返回类型
记忆化实现	内置装饰器	需手动维护数组
变量交换	a,b = b,a+b	需要临时变量
代码行数	通常更简洁	相对冗长

面试实战建议 ：

1. 先给出最直观的递归解法，然后主动优化
2. 解释每种解法时，先说明思路再写代码
3. 时间复杂度分析要贯穿始终
4. 对于Python候选人，展示 lru_cache 的使用是加分项
5. Java候选人应注意数组初始化和类型声明

在最近的一次模拟面试中，候选人A在给出滚动数组解法后，主动补充道："这种方法其实可以推广到步数为[1,2,3]的情况，只需增加一个变量c..."这种举一反三的表现直接获得了面试官的加分。