LeetCode 70.爬楼梯递归解法求助：本地正常平台仅过单个用例

核心问题1：static变量的状态污染 #

你的代码中使用了static int count = 0，static变量的生命周期覆盖整个程序运行阶段，只会初始化一次。LeetCode测试时会连续多次调用climbStairs函数（比如依次测试n=2、n=3、n=4等用例），第一次测试后count的数值不会重置，后续测试会基于之前的累加值计算，直接导致结果错误。

举个例子：

• 第一次测试n=2，count变为2，返回2，结果正确。
• 第二次测试n=3时，count初始值是2，调用climbStairs(2)会让count加2变成4，再调用climbStairs(1)加1变成5，最终返回5，但正确结果应该是3。

这就是本地单次测试正常，但LeetCode仅通过一个用例的根本原因——本地你可能只单次运行一个用例，而LeetCode是多用例连续执行。

核心问题2：递归逻辑错误 #

你的递归思路本身不符合问题的递推关系：爬n级楼梯的不同方式数，应该是climbStairs(n-1) + climbStairs(n-2)（因为最后一步要么是爬1级，要么是爬2级，两种情况的方式数相加），而不是用static变量累加子问题的结果。你的代码逻辑把每个子问题的结果直接加到全局count中，完全偏离了问题的数学模型。

修正方案 #

方案1：迭代法（最优，空间复杂度O(1)） #

不需要递归，直接用变量迭代计算斐波那契数列，避免重复计算和状态污染：

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev_prev = 1, prev = 2, current;
    for (int i = 3; i <= n; i++) {
        current = prev_prev + prev;
        prev_prev = prev;
        prev = current;
    }
    return prev;
}

方案2：记忆化递归（避免重复计算） #

如果倾向用递归，可通过记忆化存储已计算的结果，避免重复递归调用：

#include <stdlib.h>

int climbStairs(int n) {
    if (n <= 2) return n;
    // 用数组存储已计算的结果，防止重复递归
    int* memo = (int*)malloc(sizeof(int) * (n + 1));
    memo[1] = 1;
    memo[2] = 2;
    for (int i = 3; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }
    int result = memo[n];
    free(memo);
    return result;
}

方案3：基础递归（仅作逻辑演示，不推荐） #

如果只是想验证递归逻辑，正确的写法如下，但该版本会有大量重复递归，n较大时会超时，不适合LeetCode提交：

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

内容的提问来源于stack exchange，提问作者Hrachya Margaryan