1.分析題目
現(xiàn)要將石子有次序地合并成一堆测秸，要求&條件：規(guī)定每次只能選相鄰的2堆合并成新的一堆滨巴，
并將新的一堆的石子數(shù)，記為該次合并的得分骑丸。
2.思考
不難發(fā)現(xiàn)這需要進(jìn)行區(qū)間操作舌仍，我們同樣可以聯(lián)想到使用區(qū)間動(dòng)態(tài)規(guī)劃，因此可以解決子問(wèn)題重疊的問(wèn)題通危，減少時(shí)間復(fù)雜度
3.設(shè)計(jì)
通過(guò)3層for循環(huán)完成計(jì)算铸豁。計(jì)算前先初始化dp_max&dp_min變量還有計(jì)算1-n前綴和，以便后面的對(duì)比菊碟、計(jì)算
4.計(jì)算
根據(jù)
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]}
解釋一下公式节芥，它們的作用都是獲取某個(gè)區(qū)間的最大或者最小得分，原理是通過(guò)區(qū)間遍歷的方法逆害，分成很多個(gè)兩份头镊，計(jì)算前綴和，相加忍燥，
再拧晕，最后再加上區(qū)間的總前綴和進(jìn)行比對(duì)隙姿。
5.得出結(jié)果
我們直接可以用一個(gè)for循環(huán)遍歷一遍dp_max&dp_min數(shù)組獲取它們的最大或最小值
6.總結(jié)
用動(dòng)態(tài)規(guī)劃的算法來(lái)解此道題可以?xún)?yōu)化重復(fù)計(jì)算的一些問(wèn)題梅垄，因而減少時(shí)間復(fù)雜度。
#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開(kāi)始
for (int i = 1; i <= 2*n-L+1; i++) {//i=2*n+1 i:區(qū)間起點(diǎn)
int j = i + L - 1;//區(qū)間結(jié)尾
for (int k = i ; k <= j-1; k++)//k=i第1部分d結(jié)尾
{
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;
}```