c++朴素动态规划算法

在C++中，朴素动态规划（Naive Dynamic Programming）是一种解决问题的技术，常用于优化问题，特别是那些可以分解成相互独立的部分并具有最优子结构的问题。它的基本思想是将大问题分解为更小的子问题，通过存储每个子问题的解来避免重复计算。

一个简单的例子是斐波那契数列的求解。经典的递归算法会有很多重复计算，而朴素动态规划则可以通过创建一个数组来存储已经计算过的斐波那契数，以此来减少计算量：

int fibonacci(int n) {
    if (n <= 1) return n; // 基本情况

    int dp[n + 1]; // 动态规划数组
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

在这个例子中，`dp[i]` 存储了前两个数之和，避免了重复计算。