Java:: 为什么这个带有记忆的斐波那契数列的实现不起作用？

Question

我有一个关于使用记忆 (DP) 实现斐波那契数列的快速问题。我正在使用哈希表，但由于某种原因，该表似乎从未包含元素。每当从哈希表中读取一个值时，我插入了一个打印语句来打印出一些东西，但似乎这从未发生过。我觉得这是一个简单的修复，但我看不到。

  public static int getFib(int n) {
        HashMap<Integer, Integer> dictionary = new HashMap<Integer, Integer>();
        if (n <= 2)
            return 1;
        else if (dictionary.containsKey(n)) {
            System.out.println("Reading From Table");
            return dictionary.get(n);
        } else {
            int val = getFib(n - 1) + getFib(n - 2);
            dictionary.put(n, val);
            return val;
        }
    }

Answer 1

您正在递归调用 getFib()，并在每次调用时实例化一个新字典。使字典成为class级变量。

Answer 2

在您的方法之外初始化字典。 现在，您正在每个递归调用中创建一个新的 'dictionary'。

Answer 3

dictionary 是一个 local variable 所以这个变量的范围在函数 getFib.

内

如果你递归调用函数 getFib 那么每次 hash map will be created and instantiated 和 scope of the hashmap dictionary will end on returning from the function.

你可以用global variable来解决这个问题。

Answer 4

使dictionary成为成员变量而不是局部变量

private HashMap<Integer, Integer> dictionary = new HashMap<Integer, Integer>();

public static int getFib(int n) {

    // some operations
}

Java:: 为什么这个带有记忆的斐波那契数列的实现不起作用？

Java:: Why isn't this implementation of Fibonacci sequence with memoization not work?

java

algorithm

dynamic-programming

fibonacci