回忆Fibonacci不运行与常规Fibonacci解决方案

Question

所以我正在学习动态编程，我试着测试我的回忆录解决方案和普通的fibonacci解决方案。当我输入一个相当大的数字，比如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，我才能发现，在我的“回忆录”解决方案中，每次调用新地图时，这个方法都会非常慢！我绕过了这一点，将映射作为实例变量添加，如下所示：

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;
}

这大大提高了性能。