c语言斐波那契数列记忆化

斐波那契数列是指：0、1、1、2、3、5、8、13、21、34、……，在数学上，斐波那契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。

斐波那契数列的递归实现虽然简单易懂，但是由于存在大量的重复计算，导致效率较低。因此，可以使用记忆化的方法来优化斐波那契数列的计算。

记忆化的思想是将已经计算过的结果保存下来，避免重复计算。具体实现方法是使用一个数组来保存已经计算过的斐波那契数列的值，如果需要计算的值已经在数组中存在，则直接返回该值，否则进行计算并将结果保存到数组中。

以下是C语言斐波那契数列记忆化的示例代码：

#include <stdio.h>

int fib(int n, int memo[]) {
    if (memo[n] != -1) { // 如果已经计算过，直接返回结果
        return memo[n];
    }
    if (n == 0 || n == 1) { // 边界条件
        memo[n] = n;
    } else { // 递归计算
        memo[n] = fib(n-1, memo) + fib(n-2, memo);
    }
    return memo[n];
}

int main() {
    int n;
    scanf("%d", &n);
    int memo[n+1]; // 定义数组保存计算结果
    for (int i = 0; i <= n; i++) {
        memo[i] = -1; // 初始化为-1
    }
    printf("%d\n", fib(n, memo));
    return 0;
}