这个C++函数如何使用memoization？

Question

#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

上面的代码示例使用memoization来计算基于某些输入的递归公式n.我知道这使用了memoization,因为我编写了一个使用相同公式的纯递归函数,但是对于更大的值,这个更快,更快n.我之前从未使用过载体,但我做了一些研究,并且我理解它们的概念.我知道memoization应该存储每个计算值,因此它不是再次执行相同的计算,而是可以简单地检索已经计算过的值.

我的问题是:这个备忘录怎么样,它是如何工作的？我似乎无法在代码中看到它检查n的值是否已经存在.另外,我不明白的目的if(as[n]<=0).这个公式可以产生正值和负值,所以我不确定这个检查是在寻找什么.

---

谢谢,我想我已经接近理解它是如何工作的,它实际上比我想象的要简单得多.

我认为序列中的值不能为0,所以这应该对我有用,因为我认为n必须从1开始.

但是,如果零在我的序列中是可行的数字,那么我可以用另一种方法解决它？例如,如果五个永远不会出现怎么办？我只需要用五个填充矢量吗？

编辑:哇,在检查代码并键入此代码时,我收到了很多其他响应.感谢大家的帮助,我想我现在明白了.

Answer 1

if (as[n] <= 0)是支票.如果有效值可能是负面的,那么你需要一个不同的哨兵来检查.有效值是否可以为零？如果没有,那就进行测试if (as[n] == 0).这使得代码更容易编写,因为默认情况下,ints的向量用零填充.