LeetCode 746最小爬楼梯成本：递归记忆化内存溢出及结果错误问题

问题根源分析 #

递归+记忆化方案在处理大规模数组时，会遇到两个核心问题：

• 调用栈溢出：JavaScript的递归调用栈深度有限，当数组长度过大时，递归层级超出栈容量限制。
• 堆内存溢出：即使改用对象存储缓存，当数组规模极大时缓存条目过多，会占用大量堆内存导致溢出。
  而你用step作为缓存key时结果错误，大概率是递归函数的逻辑定义错误——比如错误地将递归函数定义为"到达step的成本"，而非"从step出发到顶部的最小成本"。

最优解决方案：迭代式动态规划（空间优化版） #

迭代方案完全避免递归栈的问题，同时通过空间优化将内存复杂度降到O(1)，适用于所有规模的输入。

核心逻辑

• 顶部对应数组长度的位置（如数组长度为n，顶部索引为n）。
• 到达顶部的最小成本，等于从最后一级台阶（n-1）出发的成本，与从倒数第二级台阶（n-2）出发的成本中的较小值。
• 用两个变量保存前两级台阶的最小成本，无需维护整个DP数组。

JavaScript代码实现

function minCostClimbingStairs(cost) {
    // 初始状态：从第0级或第1级出发的成本
    let prevTwo = cost[0];
    let prevOne = cost[1];
    
    for (let i = 2; i < cost.length; i++) {
        const current = cost[i] + Math.min(prevTwo, prevOne);
        prevTwo = prevOne;
        prevOne = current;
    }
    
    // 最后取从最后两级到顶部的最小值
    return Math.min(prevTwo, prevOne);
}

修正后的记忆化递归方案（仅适用于小规模数组） #

如果坚持用递归，需确保递归函数定义正确，同时用Map缓存结果：

核心逻辑

• 定义dfs(step)为从step位置出发到达顶部的最小成本。
• 当step >= cost.length时，说明已到达顶部，返回0。
• 否则，当前成本为cost[step] + min(dfs(step+1), dfs(step+2))，缓存该结果避免重复计算。

JavaScript代码实现

function minCostClimbingStairs(cost) {
    const memo = new Map();
    
    const dfs = (step) => {
        if (step >= cost.length) return 0;
        if (memo.has(step)) return memo.get(step);
        
        const res = cost[step] + Math.min(dfs(step + 1), dfs(step + 2));
        memo.set(step, res);
        return res;
    };
    
    return Math.min(dfs(0), dfs(1));
}

测试验证 #

• 测试用例1：输入[0,1,0,0]，迭代和修正后的递归方案均返回0，符合预期。
• 测试用例2：输入[1,100,1,1,1,100,1,1,100,1]，均返回6，符合预期。

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