我倾向于通过将朴素实现与记忆化混合来找到编写记忆化的最简单方法：

int fib_mem(int n);
int fib(int n) { return n <= 1 ? n : fib_mem(n-1) + fib_mem(n-2); }
int fib_mem(int n)
{
    if (lookup_table[n] == NIL) {
        lookup_table[n] = fib(n);
    }
    return lookup_table[n];
}

字符串

#include <iostream>
#define N 100

using namespace std;

const int NIL = -1;
int lookup_table[N];

void init()
{
    for(int i=0; i<N; i++)
        lookup_table[i] = NIL;
}
int fib_mem(int n) {
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}
int main()
{
    init();
    cout<<fib_mem(5);
    cout<<fib_mem(7);
}

字符串
使用完全相同的功能，这是工作正常。
您在初始化lookup_table时做错了一些事情。

由于问题是初始化，C++标准库允许您初始化序列，而无需编写for循环，从而防止您犯错误，例如使用==而不是=。
std::fill_n函数的作用是：

#include <algorithm>
//...

void initialize()
{
   std::fill_n(lookup_table, MAX, NIL);
}

字符串

有趣的概念。通过记忆加速。
还有一个不同的概念，你可以称之为编译时记忆，但实际上它是编译时预先计算所有适合64位值的斐波那契数。
斐波那契数列的一个重要属性是其值会以指数形式增长，因此，所有现有的整型数据类型都会很快溢出。
用比奈的公式，你可以计算出第93个斐波那契数是最后一个适合64位无符号值的数。
在编译期间计算93个值是一个非常简单的任务。
我们首先将计算斐波那契数的默认方法定义为constexpr函数：

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

字符串
有了这个，斐波那契数可以很容易地在运行时计算。然后，我们用所有的斐波那契数填充std::array。我们还使用constexpr，并使其成为一个带有可变参数包的模板。
我们使用std::integer_sequence为索引0，1，2，3，4，5，.创建一个斐波那契数。
这很简单，也不复杂：

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

型
这个函数将被输入一个整数序列0，1，2，3，4，.并返回一个std::array<unsigned long long, ...>和相应的斐波那契数。
我们知道我们最多可以存储93个值。因此我们创建了下一个函数，它将调用上面的整数序列1，2，3，4，.，92，93，如下所示：

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

型
现在，终于，

constexpr auto FIB = generateArray();

型
将给予我们一个编译时的std::array<unsigned long long, 93>，名为FIB，包含所有的Fibonacci数。如果我们需要第i个Fibonacci数，那么我们可以简单地写FIB[i]。在运行时不会有计算。
我不认为有更快的方法来计算第n个斐波那契数。
请参阅下面的完整程序：

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------

// Test
int main() {

    // Print all possible Fibonacci numbers
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)

        std::cout << i << "\t--> " << FIB[i] << '\n';

    return 0;
}

型
使用Microsoft Visual Studio Community 2019版本16.8.2开发和测试。
另外还使用clang11.0和gcc10.2进行了编译和测试
语言：C++17

在initialize()函数中有一个错误：

void initialize() {
    for(int i = 0; i < MAX; i++) {
        lookup_table[i] == NIL; // <- mistake
    }
}

字符串
在所指的行中，您比较lookup_table[i]和NIL（并且不使用结果），而不是将NIL分配给lookup_table[i]。
对于赋值，应该使用=而不是==。
此外，在这种情况下，最正确的做法是编译程序时启用所有警告。例如，MS VC++显示以下警告：

warning C4553: '==': operator has no effect; did you intend '='?

型

这个错误出现在初始化函数上（你使用了比较运算符'=='，而你想要一个属性运算符'='）。但是，在语义上，你不需要用-1（NIL）初始化look_table，因为Fibonacci的结果永远不会是0（零）;所以，你可以用零初始化它。看看下面的最终解决方案：

#include <iostream>

#define NIL 0
#define MAX 1000

long int lookup_table[MAX] = {};

using namespace std;

long int fib(int n) {
    if(n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

long int fib_mem(int n) {
    assert(n < MAX);
    if(lookup_table[n] == NIL) {
        if(n <= 1)
            lookup_table[n] = n;
        else
            lookup_table[n] = fib_mem(n-1) + fib_mem(n-2);
    }
    return lookup_table[n];
}

int main() {
    int n;
    long int fibonnaci, fibonacci_mem;
    cout << " n = "; cin >> n;

    // naive solution
    fibonnaci = fib(n);

    // memoized solution
    // initialize();
    fibonacci_mem = fib_mem(n);

    cout << fibonnaci << endl << fibonacci_mem << endl;

    return 0;
}

字符串

在我的解决方案中，我使用一个map而不是数组来存储memo。

#include <iostream>
#include <map>
using namespace std;

map<int, unsigned long long> memo;

unsigned long long fibo(int n) {
    if (memo[n]) {
        return memo[n];
    }

    if (n <= 1) {
        return n;
    }
    memo[n] = fibo(n-1) + fibo(n-2);
    return memo[n];
}

int main() {
    int n; 
    cin >> n;
    cout << "Ans: " << fibo(n);
    return 0;
}

字符串