根据给定斐波那契递归函数创建记忆算法

Question

对于学校作业，我们必须创建一个记忆式斐波那契函数，该函数重用计算斐波那契的递归实现。

设计记忆功能以使其利用现有功能的好方法是什么？到目前为止，这是我的实现：

基类：

public int computeFibonacci(int position) {
    assertPosition(position);

    if (position < 2) {
        return 1;
    }
    return computeFibonacci(position - 1) + computeFibonacci(position - 2);
}

继承的类：

public int computeFibonacci(int position) {
    assertPosition(position);

    if (position < 2) {
        return 1;
    }

    if (this.memoizedList.containsKey(position)) {
        return this.memoizedList.get(position);
    }
    int result = super.computeFibonacci(position - 1) + super.computeFibonacci(position - 2);
    this.memoizedList.put(position, result);
    return result;
}

Answer 1

您的子类版本未充分利用缓存的值。例如，如果您调用computeFibonacci(5)，并且memoizedList不包含该键，则即使它们已经被缓存，您也将调用super.computeFibonacci(4)和super.computeFibonacci(3)。相反，您应该致电super.computeFibonacci(5)。

public int computeFibonacci(int position) {
    assertPosition(position);

    if (position < 2) {
        return 1;
    }

    if (this.memoizedList.containsKey(position)) {
        return this.memoizedList.get(position);
    } else {
        int result = super.computeFibonacci(position);
        this.memoizedList.put(position, result);
        return result;
    }
}