LeetCode 70爬楼梯：递归分支记忆化及斐波那契解法疑问

先看你当前的递归分支解法：它通过枚举所有可能的步数组合来统计路径数量，本质是暴力枚举所有有效路径，但因为没有记忆化，重复计算极多，处理大数自然会超时。

疑问1：能否为该递归分支写法实现记忆化？ #

你的当前写法直接加记忆化非常不现实——因为递归函数的参数是combination数组，每次调用都会生成新数组，不仅作为记忆化的key会极度冗余，而且数组的哈希/比对成本极高。

要给这个思路加记忆化，必须先改造递归的参数：把传递“已走的步数组合”改成传递“当前已走的总步数”，因为决定后续走法的只有当前总步数，和具体走了哪些1/2步无关。改造后的记忆化版本如下：

var climbStairs = function(n) {
    // 记忆化缓存：key是当前已走步数，value是从该步数到终点的路径数
    const memo = new Map();

    let dfs = (currentStep) => {
        // 终止条件：已走步数等于n，这是1条有效路径
        if (currentStep === n) {
            return 1;
        }
        // 已走步数超过n，无效路径，不计入
        if (currentStep > n) {
            return 0;
        }
        // 先查缓存，存在则直接返回
        if (memo.has(currentStep)) {
            return memo.get(currentStep);
        }
        // 递归计算：走1步后的路径数 + 走2步后的路径数
        const count = dfs(currentStep + 1) + dfs(currentStep + 2);
        // 存入缓存
        memo.set(currentStep, count);
        return count;
    };

    return dfs(0);
};

如果你非要保留“记录路径”的分支写法（但完全没必要统计数量时这么做），其实也可以用缓存记录某一步数对应的路径数，但这样做和上面的写法本质一致，只是多了记录路径的逻辑，反而更冗余。

疑问2：为什么斐波那契写法用递归调用相加，如何判断用相加还是分支写法？ #

两种写法的核心区别： #

• 你的分支写法：是在枚举所有具体路径，每找到一条有效路径就计数+1（通过push数组最后取长度），属于“穷举法”。这种写法的目的是得到所有可能的走法细节，但路径数量是指数级增长的，n大了必然超时。
• 斐波那契式相加写法：是在统计子问题的解数之和，属于“动态规划递归版”。它的逻辑是：

  当前在currentStep位置，走到终点的走法数 = 走1步到currentStep+1的走法数 + 走2步到currentStep+2的走法数
  因为从currentStep出发，只有两种选择，每种选择对应的后续走法数是独立的，所以总走法数是两者的和。

判断用哪种写法的依据： #

• 如果题目要求输出所有具体的走法路径，必须用分支枚举的写法（但要注意n不能太大，否则内存和时间都会爆炸）；
• 如果题目只要求统计走法的数量，用相加的状态转移写法（不管是递归记忆化还是迭代动态规划），效率极高，时间复杂度是O(n)，空间复杂度可以优化到O(1)。

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