java - Memozied Fibonacci 不运行与常规 Fibonacci 解决方案

Question

所以我正在学习动态规划，我正在尝试测试我的内存解决方案与普通斐波那契解决方案。 当我输入相当大的数字(如 43)时，我的内存解决方案需要永远运行，而正常的解决方案会在 5 - 6 秒后运行。这是否意味着我的备忘解决方案实际上并未存储已经看到的结果？

这是我的传统解决方案:

public static int fibonacci(int i) 
{
    if(i == 0) 
    {
        return 0;
    }
    if(i <= 2) 
    {
        return 1;
    }
    return fibonacci(i - 1) + fibonacci(i - 2);
}

内存解决方案:

public static int fibonacci(int n) 
{
    Map<Integer, Integer> memo = new HashMap<>();
    if(n == 0) 
    {
        return 0;
    }
    if(n <= 2)
    {
        return 1;
    }
    if(memo.containsKey(n))
    {
        return memo.get(n);
    }
    int result = fibonacci(n - 1) + fibonacci(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(fibonacci(n));
}

任何关于为什么会这样的解释将不胜感激:)

Answer 1

感谢@shmosel，我能够弄清楚在我的“记忆化”解决方案中，每次调用该方法时我都在调用一个新 map ，导致它非常慢!我通过将 map 添加为实例变量来规避此问题，如下所示:

private static Map<Integer, Integer> memo = new HashMap<>();

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

    return result;
}

这大大提高了性能。