LeetCode 70爬楼梯：两种解法的int限制问题及差异问询

嘿，我来帮你把这两个问题讲明白～

一、为什么第一种递归解法在n≥44时失效？ #

你的递归解法本质是直接计算斐波那契数列，但这个写法有个致命问题：大量重复计算。举个例子，计算fib(5)时，需要算fib(4)和fib(3)；计算fib(4)又要算fib(3)和fib(2)——这里fib(3)就被重复计算了两次。随着n增大，重复计算的次数会呈指数级增长（时间复杂度是O(2ⁿ)）。

当n到44的时候，需要执行的计算量已经大到超出LeetCode的时间限制了，所以会超时失败。另外，递归调用还会占用调用栈空间，但这里主要的问题还是超时，因为指数级的运算量实在太夸张了。

你的递归代码格式化后是这样的：

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

二、两种解法的核心差异是什么？ #

这两种解法的核心区别在于计算方向、效率和资源利用：

• 计算方向：
  • 递归是自顶向下：从目标n出发，把问题拆成更小的子问题（n-1和n-2），直到碰到base case（n≤2）再回溯求和。
  • 迭代是自底向上：从最小的base case（n=1、n=2）开始，一步步计算到n对应的结果，每一步的结果都依赖之前已经算好的值。
• 时间效率：
  • 递归的时间复杂度是O(2ⁿ)，因为有大量重复计算，n稍微大一点就会超时。
  • 迭代的时间复杂度是O(n)，每个子问题只计算一次，效率高很多，能通过LeetCode的时间限制。
• 空间利用：
  • 递归需要占用调用栈空间，栈深度是O(n)，如果n特别大还可能触发栈溢出（不过这里n=44还没到栈溢出的程度，主要是超时）。
  • 你的迭代解法用了一个数组存所有中间结果，空间复杂度是O(n)，其实还可以优化成O(1)——只需要两个变量保存前两个值就行，不用数组。
• 重复计算问题：
  • 递归完全没处理重复子问题，同一个子问题会被计算上百上千次。
  • 迭代通过数组（或者变量）把已经算好的子问题结果存起来，后续直接复用，没有重复计算。

另外补充一下：你的迭代解法在n≥46时返回负数，是因为整数溢出。Java里int的最大值是2³¹-1=2147483647，爬楼梯的第47项是2971215073，已经超过int的最大值了，溢出后会变成负数（因为Java用补码存储整数，溢出后最高位变成1，代表负数）。解决办法可以把变量改成long类型，最后再转成int（如果结果在int范围内的话），或者用BigInteger处理超大数。

你的迭代代码格式化后是这样的：

class Solution { 
    public int climbStairs(int n) { 
        if (n <= 2) return n; 
        int[] allWays = new int[n]; 
        allWays[0] = 1; 
        allWays[1] = 2; 
        for (int i = 2; i < n; i++){ 
            allWays[i] = allWays[i-1] + allWays[i-2]; 
        } 
        return allWays[n-1]; 
    } 
}

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