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

上面的代码示例使用记忆来基于某些输入" n"来计算递归公式。我知道这使用了记忆，因为我编写了一个使用相同公式的纯递归函数，但是对于更大的n值，此函数要快得多。我以前从未使用过向量，但是我已经做过一些研究并且了解它们的概念。我知道备忘录应该存储每个计算出的值，因此与其重复执行相同的计算，它可以简单地检索已经计算出的值。

我的问题是：这种记忆如何运作？我似乎无法在代码中看到它检查该点是否已经存在n的值。而且，我不理解if(as [n] <= 0)的目的。此公式可以产生正值和负值，因此我不确定此检查要查找什么。

谢谢，我想我已经接近了解它的工作原理了，实际上比我想象的要简单一些。

我认为序列中的值永远不能为0，因此这应该对我有用，因为我认为n必须从1开始。

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

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

解决方案

如果是if(as [n] <= 0)。如果有效值可以像我们说的那样为负，则需要使用其他标记来进行检查。有效值可以为零吗？如果不是，则只需进行测试if(as [n] == 0)。这使代码更易于编写，因为默认情况下，ints的向量用零填充。

如果公式可以同时产生正值和负值，则此函数存在严重的错误。检查if(as [n] <= 0)应该检查它是否已经缓存了该计算值。但是，如果公式可以为负，则此函数会大量重新计算该缓存的值...

它可能真正想要的是一个vector <pair <bool，unsigned>>`，其中bool表示该值是否已计算。

该代码似乎被错误地检查了(as [n] <= 0)，并重新计算了该函数的负值(似乎近似于其他所有值)。这使得工作规模使用n线性化，而不是使用递归解决方案2 ^ n线性化，因此运行速度快得多。

不过，更好的检查方法是测试(as [n] == 0)是否在我的系统上运行速度快3倍。即使该函数可以返回0，但0值仅表示将需要稍长的时间来计算(尽管如果0是一个频繁返回的值，则我们可能需要考虑一个单独的向量来标记该值是否已被计算，而不是使用单个向量存储函数的值以及是否已计算出该值)

所发布的代码仅能记住40％的时间(准确地是当记忆值是正数时)。正如Chris Jester-Young指出的那样，正确的实现将改为检查if(as [n] == 0)。或者，可以将记忆代码本身更改为" as [n] = mod(-4 * a(n-1)-4 * a(n-2)，65535);"

(即使" == 0"检查也会在记住的值为0时花费很多精力。幸运的是，在情况下，这永远不会发生！)

这段代码中有一个错误。对于as [n] <= 0，它将继续重新计算as [n]的值。它将记住a的值，结果为正。它比没有备忘的代码快得多，因为as []的正值足够多，因此递归可以快速终止。我们可以通过使用大于65535的值作为参量来改善这一点。向量扩展时，向量的新值初始化为零。