石子合并 --- 动态规划

1.分析题目
现要将石子有次序地合并成一堆，要求&条件：规定每次只能选相邻的2堆合并成新的一堆，
并将新的一堆的石子数，记为该次合并的得分。
2.思考
不难发现这需要进行区间操作，我们同样可以联想到使用区间动态规划，因此可以解决子问题重叠的问题，减少时间复杂度
3.设计
通过3层for循环完成计算。计算前先初始化dp_max&dp_min变量还有计算1-n前缀和，以便后面的对比、计算
4.计算
根据
dp_max[i][j]=max{dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]+sum[j]-sum[k-1]}
dp_min[i][j]=min{dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]+sum[j]-sum[k-1]}
解释一下公式，它们的作用都是获取某个区间的最大或者最小得分，原理是通过区间遍历的方法，分成很多个两份，计算前缀和，相加，
再，最后再加上区间的总前缀和进行比对。
5.得出结果
我们直接可以用一个for循环遍历一遍dp_max&dp_min数组获取它们的最大或最小值
6.总结
用动态规划的算法来解此道题可以优化重复计算的一些问题，因而减少时间复杂度。

#include<iostream>
#include<cstring>
#include <algorithm>
using namespace std;
int dp_max[510][510], dp_min[510][510], sum[510], v = 0, dp_mint[5010];
int main()
{
    int n, s;
    cin >> n;
    
    memset(dp_max, 0, sizeof(dp_max));
    memset(dp_min, 0, sizeof(dp_min));
    memset(sum, 0, sizeof(sum));
    memset(dp_mint, 0, sizeof(dp_mint));
    
    for (int i = 1; i <= n; i++) {
        cin >> s;
        dp_mint[i] = s; v += s; sum[i] = v;
    }
    for (int i = n + 1; i <= n * 2; i++) {
        dp_mint[i] = dp_mint[i - n]; v += dp_mint[i]; sum[i] = v;
    }
    //初始化MIN
    for (int u = 1; u <= 2 * n; u++)
    {
        for (int j = u+1; j <= 2 * n; j++)
        {
            dp_min[u][j] = 500000000;
        }
    }
    for(int L=2;L<=n;L++)//从2开始
        for (int i = 1; i <= 2*n-L+1; i++) {//i=2*n+1 i:区间起点
            int j = i + L - 1;//区间结尾
            for (int k = i ; k <= j-1; k++)//k=i第1部分d结尾
            {
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum[j] - sum[i - 1]);
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    int q;
    int Max1 = 0; int Min1 = 500000000;
    for (q = 1; q <= n; q++)
    {
        Max1 = max(Max1, dp_max[q][q + n - 1]);
        Min1 = min(Min1, dp_min[q][q + n - 1]);
    }
    cout << Min1<<endl <<  Max1;
    return 0;
}```