本文共 1068 字，大约阅读时间需要 3 分钟。

台阶问题求解方法与实现

递归方法与分析

台阶问题，核心是计算从底部到达顶部所需跳步的总方法数。通过递推公式 f(n) = f(n-1) + f(n-2)，我们可以逐步构建解决方案。

思路阐述

递归方法通过将大问题分解为小问题来求解。假设 f(n) 表示走 n 个台阶的总方法数，那么当处理到最后一步时，有两种可能性：从倒数第二步跳一步到达最后一步，或者从倒数第三步跳两步到达最后一步。这两种情况的总和即为 f(n)。

具体来说：

• 当 n=1 时，只有1种方法。
• 当 n=2 时，有两种方法：[1,1] 和 [2]。

递归代码

class Solution:
    public:
        int climbStairs(int n):
            if n <= 2:
                return n
            return climbStairs(n-1) + climbStairs(n-2)

优缺点分析

此递归方法采用了分治法，简化了问题，但会导致对较大的 n 值来说递归深度过大，造成超时问题，且多次计算相同子问题。

迭代方法与实现

方法改进

迭代方法通过缓存中间结果，避免重复计算，提升效率。

思路阐述

我们可以用循环来逐步计算每一步的台阶数目，避免递归带来的额外计算量。具体方法如下：

• 初始化两个变量 f1 和 f2 分别存储前两步的解。
• 根据递推公式 fn = f1 + f2 实时更新，最终得到第 n 步的解。

迭代代码

class Solution:
    public:
        int climbStairs(int n):
            f1 = 1
            f2 = 2
            fn = 0
            if n <= 2:
                return n
            for i in range(2, n):
                fn = f1 + f2
                f1 = f2
                f2 = fn
            return fn

优点分析

迭代方法消除了递归方法的函数调用开销，空间复杂度为 O(1)，时间复杂度为 O(n)，执行效率显著提升，避免了递归递归带来的性能问题。

结论

两种方法各有优劣，递归方法简单易懂，迭代方法在大数情况下更高效。根据具体需求选择合适的实现方案。