算法：区间dp
什么是区间dp
区间dp就是在区间上进行动态规划，求解一段区间上的最优解；该问题的求解思路主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。
核心思路
先把这个区间分割成一小个一小个区间，求解小区间的最优解，再合并小区间得到大区间的最优解。在代码上，枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，终点也就知道了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
for(int len=1;len<=n;len++){//长度
for(int l=1;l<=n-len+1;l++){//起点
int r=l+len-1;//终点
for(int k=l;k<r;k++){//分割点 更新小区间最优解
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+....);
}
}
}线性区间dp
例题1 洛谷p1775
题意：有n个石子排成一排，每个石子有有一定的质量，现在要将这n个石子合并成一个，每相邻两个石子可以合并成一个，代价为质量之和。求最小代价。
分析：先用前缀和求代价，这样可以知道区间的代价和。令dp[i][j]表示石子中第i堆到第j堆合并的最小代价，则l~r堆合并 =min（原来，分割点k左部分重量+分割点k右部分重量+合并后两堆总重量）
核心代码也就是
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
#include<bits/stdc++.h>
using namespace std;
int a[1000],sum[1000],f[310][310];
int main(){
int n;cin>>n;memset(f,0x3f3f,sizeof(f));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i],f[i][i]=0;
for(int len=1;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}环状区间dp
例题2 洛谷p1880
题意：给n个石子，每个石子都有质量，将石子围成一个圈，每次可以选择相邻的石子合并成一堆，代价为质量之和，现在想将n个石子合并成1个，求最大代价和最小代价。
分析：先用前缀和求出区间内的代价和。此题与例1不同的是，这是个圈，我们可以将前n-1个数放在第n个数之后构成一个线性的环状序列。样例为4 5 9 4，可以看成4 5 9 4 4 5 9。与例一相同做法啦！
#include<bits/stdc++.h>
using namespace std;
int main(){
int fmax[310][310];
int f[310][310];
int sum[1000],a[1000];
int n;cin>>n;
memset(f,0x3f3f,sizeof(f));
memset(fmax,0,sizeof(fmax));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i],f[i][i]=0,fmax[i][i]=0;//前n个数
for(int i=1;i<n;i++){//后n-1位
sum[i+n]=sum[i+n-1]+a[i];
f[i+n][i+n]=0;
fmax[i+n][i+n]=0;
}
for(int len=1;len<=n;len++){//长度还是n
for(int l=1;l<=2*n-len+1;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
fmax[l][r]=max(fmax[l][r],fmax[l][k]+fmax[k+1][r]+sum[r]-sum[l-1]);
}
}
}
int amax=0,amin=0x3f3f3f3f;
for(int i=1;i<=n;i++){
amax=max(amax,fmax[i][i+n-1]);
amin=min(amin,f[i][i+n-1]);
}
cout<<amin<<endl;
cout<<amax<<endl;
return 0;
}例题分析：
例3洛谷p4170
题意：给定一个长度为n的目标字符串，初始什么也没有，你可以选择一段连续的字符串变成相同字符。例如目标是RGBGR,第一次把木板涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR。
分析：枚举长度为1，涂色次数为1
长度为2，如果颜色相同，次数为1，如果颜色不同，次数为2
长度为3，尝试写状态转移方程。如果首尾相同，则可以一个刷子涂满整个区间。所以
f[l][r]=min(f[l+1][r], f[l][r-1])。如果首尾不同则f[l][r]=min(f[l][k] + f[k+1][r],f[l][r])。
写出核心代码：
if(s[l]==s[r]){
f[l][r]=min(f[l][r-1],f[l+1][r]);
}
else{
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
}
}#include<bits/stdc++.h>
using namespace std;
int main(){
string s;cin>>s;
int n=s.size();
int f[100][100];memset(f,0x3f3f3f3f,sizeof(f));
for(int i=0;i<n;i++)f[i][i]=1;//长度为1
for(int len=2;len<=n;len++){
for(int l=0;l<n;l++){
int r=l+len-1;
if(r>=n)break;
if(s[l]==s[r]){
f[l][r]=min(f[l][r-1],f[l+1][r]);
}
else{
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
}
}
}
}
cout<<f[0][n-1]<<endl;
return 0;
}例4洛谷p3205
题意：有n个人以及目标队列。刚开始n个人随机站。
第一个人直接插入空的当前队形中。对从第二个人开始的每个人，如果他比前面那个人高（ℎh 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（ℎh 较小），那么将他插入当前队形的最左边。以此类推。
求有多少种初始队列可以获得目标队列。
分析：当只有1个人的时候只有1种。
当有2个人的时候，如果前面那个人比后面那个人高则不存在，如果后面那个人比前面那个人高，则有两种（第一种是先放入前面那个人再放入后面那个人，第二种是先放后面那个人再放前面那个人）
当有3个人的时候，如果第一个人大于第三个人时，可以加上后面两个人的状态，如果第二个人小于第三个人时，可以加上前面两个人的状态，也就是
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=19650827;
int main(){
int n;cin>>n;int a[n+10];
for(int i=1;i<=n;i++)cin>>a[i];
int f[n+10][n+10];//fxy x先入队列，y最后入队列
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=1;//长度为1
for(int len=2;len<=n;len++){
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
if(len==2){
if(a[l]>a[r])f[l][r]=0;
else {
f[l][r]=1;f[r][l]=1;
}
}
else{
if(a[l]<a[r]){
f[l][r]+=f[r-1][l];
}
if(a[r-1]<a[r]){
f[l][r]+=f[l][r-1];
}
f[l][r]%=mod;f[r][l]%=mod;
if(a[l]<a[l+1]){
f[r][l]+=f[r][l+1];
}
if(a[l]<a[r]){
f[r][l]+=f[l+1][r];
}
f[l][r]%=mod;f[r][l]%=mod;
}
}
}
cout<<(f[1][n]+f[n][1])%mod<<endl;
return 0;
}原文地址：https://blog.csdn.net/m0_74310050/article/details/140417689
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！