判断以下代码是否为求解第N个斐波那契数的记忆化正确实现

首先明确结论：你的代码功能上可以正确计算斐波那契数列第N项，但不属于memoization（记忆化）的实现，本质是带全局结果缓存的自底向上动态规划方案，你对memoization的核心认知存在一点偏差。

认知误区说明 #

你理解的「借助更小输入的输出来推导当前输入结果」是整个动态规划方法的通用核心，不是memoization独有的特征。memoization是动态规划的一种具体实现形式，核心特征是自顶向下、按需计算：

• 调用函数求解目标值f(n)时，首先检查缓存中是否已经存在n对应的计算结果，存在则直接返回
• 缓存不存在结果时，才拆分求解所需的子问题f(n-1)、f(n-2)，子问题求解过程中同样遵循「先查缓存、再计算」的逻辑
• 子问题计算完成后，将结果写入缓存，再返回给上层调用

而你的实现逻辑是：发现目标n超出当前已计算的数列长度时，从已有的最大已知项开始，通过循环逐次递推直到算出f(n)，是从最小子问题出发一路向上推导到目标值的自底向上思路，不属于记忆化范畴。

现有代码的可优化点 #

你的代码计算逻辑本身没有错误，且全局静态缓存可以避免多次调用时重复计算之前已经得到的结果，单线程场景下效率合格，但存在几个小问题：

• 类名拼写错误：Fibonaci正确拼写应为Fibonacci
• 数值溢出风险：int类型的最大值为2^31-1，当n大于46时计算结果就会超出int范围溢出，建议替换为long或BigInteger类型存储结果
• 线程安全问题：全局静态的ArrayList没有做同步处理，多线程并发调用时会出现数据错乱

其他可选实现方案 #

1. 标准自顶向下记忆化（memoization）实现 #

完全符合记忆化的实现逻辑，用哈希表做缓存，递归求解时优先读取缓存：

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Fibonacci {
    private static final Map<Integer, Long> memo = new HashMap<>();
    static {
        memo.put(0, 0L);
        memo.put(1, 1L);
    }

    public static long fibByMemo(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        long result = fibByMemo(n - 1) + fibByMemo(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        System.out.println(fibByMemo(n));
    }
}

这种实现的优势是逻辑完全贴合斐波那契的递推公式，不会计算和目标n无关的子问题；缺点是递归深度过大时会出现栈溢出，不适合n特别大的场景。

2. 空间优化的自底向上实现 #

计算f(n)时只需要用到前两项的结果，不需要存储整个数列，空间复杂度可以从O(n)降到O(1)：

public static long fibOptimized(int n) {
    if (n == 0) return 0L;
    if (n == 1) return 1L;
    long prevPrev = 0, prev = 1;
    long current = 0;
    for (int i = 2; i <= n; i++) {
        current = prevPrev + prev;
        prevPrev = prev;
        prev = current;
    }
    return prev;
}

这种实现没有递归开销，性能稳定，是工程中计算斐波那契最常用的方案。

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