c++经典的递归案例：计算斐波那契数列的第n项（使用动态规划优化）

c++经典的递归案例：计算斐波那契数列的第n项（使用动态规划优化）

#include <iostream>

// 经典的递归案例：计算斐波那契数列的第n项（使用动态规划优化）
int fibonacci(int n, int memo[]) {
    // 基本情况：如果n为0或1，返回n
    if (n <= 1) {
        return n;
    } else if (memo[n] != -1) {
        // 如果已经计算过第n项，直接返回存储的值
        return memo[n];
    } else {
        // 递归调用：计算第n项，并将结果存储在memo数组中
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        return memo[n];
    }
}

int main() {
    // 计算斐波那契数列的第10项
    const int n = 10;
    int memo[n + 1];

    // 初始化memo数组为-1
    for (int i = 0; i <= n; ++i) {
        memo[i] = -1;
    }

    // 输出第10项斐波那契数列
    std::cout << "斐波那契数列第" << n << "项是：" << fibonacci(n, memo) << std::endl;

    return 0;
}