Java记忆化实现斐波那契：数组初始化位置影响执行时长的疑问

嘿，我来帮你拆解这个问题，核心原因其实是记忆化的本质被你无意间破坏了！

两种初始化方式的本质区别 #

1. 数组作为类静态成员（方法外初始化）

当你把mem定义为类的静态变量时：

public class FiboMemoization { 
    public static long [] mem = new long[41]; 
    public static long fibo(int n){ 
        // ... 递归逻辑
    } 
}

这个数组是全局唯一的——所有递归调用的fibo方法都会共享同一个mem数组。比如你计算fibo(40)时，fibo(39)计算完会把结果存在mem[39]，后续fibo(40)调用fibo(38)时，fibo(38)又会复用mem[39]已经计算好的部分，完全不会重复计算。这才是记忆化递归的正确用法，时间复杂度是O(n)，所以跑起来只需要1ms。

2. 数组在方法内初始化

当你把mem放在fibo方法里初始化时：

public static long fibo(int n){ 
    long [] mem = new long[41]; 
    // ... 递归逻辑
}

每次调用fibo，都会新建一个全新的mem数组！也就是说：

• 调用fibo(40)时，会创建一个mem数组；
• 递归调用fibo(39)时，又会创建另一个完全独立的mem数组；
• 同理，fibo(38)、fibo(37)...每个递归层级都会有自己的mem数组，完全没法共享之前计算的结果。

这就等于你完全没做记忆化，退化成了最原始的暴力递归——时间复杂度是O(2^{n)，n=40的时候，2}40是一个约1万亿的数，CPU要算超级多重复的子问题，所以耗时16秒完全合理。

额外的小优化 #

你的代码里还有一行多余的逻辑：

else if(mem[n] != 0) 
    mem[n] = mem[n];

这行完全没必要，因为前面已经判断了if(mem[n] == 0)才进入分支，所以这个else if永远不会触发，可以删掉让代码更简洁。

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