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]` 存储了前两个数之和，避免了重复计算。

相关问题

算法设计与分析--求最大子段和问题（蛮力法 分治法 动态规划法 C++实现

最大子段和问题是指在一个数列中找到一个子序列，使得该子序列中所有元素的和最大。以下是三种常见的算法实现：

1. 蛮力法

蛮力法是最朴素的解法，它的时间复杂度为 $O(n^2)$。具体实现如下：

int maxSubArray(int nums[], int n) {
    int ans = INT_MIN;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            ans = max(ans, sum);
        }
    }
    return ans;
}

2. 分治法

分治法的时间复杂度为 $O(n\log n)$，它将问题分成三个部分：求解左半部分的最大子段和、求解右半部分的最大子段和、求解跨越中点的最大子段和。具体实现如下：

int maxSubArray(int nums[], int left, int right) {
    if (left == right) return nums[left];
    int mid = left + (right - left) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossMax = nums[mid];
    int sum = nums[mid];
    for (int i = mid - 1; i >= left; i--) {
        sum += nums[i];
        crossMax = max(crossMax, sum);
    }
    sum = crossMax;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        crossMax = max(crossMax, sum);
    }
    return max(leftMax, max(rightMax, crossMax));
}

3. 动态规划法

动态规划法的时间复杂度为 $O(n)$，它定义了一个状态数组 $dp$，其中 $dp[i]$ 表示以 $i$ 结尾的最大子段和。具体实现如下：

int maxSubArray(int nums[], int n) {
    int dp[n];
    dp[0] = nums[0];
    int ans = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        ans = max(ans, dp[i]);
    }
    return ans;
}

以上是三种常见的算法实现，需要注意的是，在实际应用中，我们还可以使用其他优化方法，如前缀和、后缀和、单调栈等，以进一步提高算法效率。