区间DP常用模板所有区间DP问题如下：一维为枚举区间长度，一般len=1用于初始化，枚举从len=2开始，二维枚举开始点I (自动获得右端点j，j=i len - 1 () ) )
"预处理长度为1时" for(intI=1； i=n； I ) { dp[i][i]='初始值'； }长度为2时开始进行推送处理' for(intlen=2； len=n； len ()区间长度(for ) intI=1； i len - 1=n； I ) )枚举起点(int j=i len - 1； “区间终点”for(intk=I； k j； k ) )列举分割点，给出状态转移方程(DP[I][j]=max(DP[I][j]，dp[i][k] dp[k 1][j] i到j的代价)； }假设字符串的起点下标为s，长度为len，终点下标为s len-1，具体是求max还是求min根据题意不同为从i到j共有j-i种划分方式，也可以写最里面的for循环
for(intk=I1； k=j； k ) DP[I][j]=max(DP[I][j]，dp[i][k-1] dp[k][j] i到j的代价)； 282 )合石主题说明n块石头排成一列，其编号为1、2、3、…、n。
石头堆有一定的质量，可以用整数来描述，现在把这n个石头堆组成一个堆。
每次只能合并相邻的两堆，合并的代价是这两块石头的质量之和，合并后与这两块石头山相邻的石头与新山相邻，合并时根据选择的顺序不同，合并的总代价也不同。
问题是找到合理的方法，使总成本最小，输出最小成本。
输入格式
第一行中的一个数n表示碎石堆的数量n。
第二行中的第n个表示每堆石头的质量(均在1000以下)。
输出格式
输出表示最小成本的整数。
数据范围
1N300
输入样例：
4
1 3 5 2
输出样例：
22
Hint：
四座石头山各1 3 5 2，我们可以先合并一两座山，代价得到4，452，又合并一两座山，代价得到9，9 2，再次合并得到11，总代价为4 9 11=24；
如果步骤2先合并2，3堆，则成本为7，47，最后合并成本为11，总成本为4 7 11=22。
分析：
核心：这是每次合并分为两部分进行合并，从进行合并的两部分中选出的又是该部分中可以选择的最小合并方式，最后合并一定要合并左连续部分和右连续部分，选择其中的最小值
但是，无论k从何处分离，分为任何两个部分，从I到j的最后合并的代价一定是a[i] a[i 1] …… a[j]之和。 这里采用前缀和的思想，采用s[j]-s[i-1]即可。
3至6合并的方式： (3，6 )i=3，j=6
一、(3，3 ) ) 4，6 ) )。
() (3，4 ) (5，6 ) )。
三、(3，5 ) ) 6，6 ) )。
() (3，6 )与) 3等价，由于从3到6依次合并，所以有j-i=6-3=3这3种方式
初始化问题：
如果初始化长度为1的合并，则成本为0，即dp[i][[i]=0，因为只有您和您可以合并。
因为是求出最小值，在长度上是未知的，所以被初始化为无限大。
代码实现# include iostream # include cstring # defineread (x ) scanf )、x ) using namespace std； const int N=310，INF=0x3f3f3f3f； int dp[N][N]； int s[N]； ' s数组前缀和' int main () { int n； 读取(n； for(intI=1； i=n； I )读取) s[I]，s[i]=s[i-1]； '输入数据并求出前缀和。' '如果先前初始化长度为1，即dp[i][i]，dp[i][i]初始化为0，否则为无限大' memset(DP，0x3f，sizeof dp )； for(intI=1； i=n； I ) dp[i][i]=0； "然后，从长度2开始递归处理. "
for (int len=2;len<=n;len++) "长度" for (int i=1;i+len-1<=n;i++) { "起点" int l=i,r=i+len-1; "起点为i，终点为i+len-1" for (int k=l;k<r;k++) dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]); } printf("%d",dp[1][n]); return 0;}最终dp数组是一个上三角矩阵，上三角存储各种起点、终点下的最小合并代价，f[1][n]就是我们需要的以1号为起点，n号为终点，长度为n的最小合并代价。
且斜对角线就表示长度，每一次for的len循环，就更新一次斜对角线，直到更新到最后一次dp[1][n]。
除了按长度枚举，也可以倒着枚举，因为只要保证每种状态都被提前计算即可。
我们注意到求dp[i][j]时，会用到dp[i+1]到dp[n]行的数据以及dp[i]行的dp[i][i]到dp[i][j-1]，我们也可以从上三角的最下面，dp[n][n]开始枚举，从下到上逐行更新。
求dp[3,6]时，可以分为上面提到的三种合并方式，因此只会用到dp[3,3]+dp[4,6] 、 dp[3,4]+dp[5,6]、dp[3,5]+dp[6,6]
由于第n行只有dp[n][n]，可以用以初始化，然后从第n-1行开始处理。
这样i就是起点，j就是终点。
for (int i=n-1;i>=1;i--) "起点" for (int j=i;j<=n;j++) "终点" for (int k=i;k<j;k++) //当j==i时就不会走这个for循环，或者直接让j=i+1开始循环 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]); 记忆化搜索 #include <iostream>#include <cstring>#define read(x) scanf("%d",&x)using namespace std;const int N=310,INF=0x3f3f3f3f;int f[N][N];int s[N];int dp(int i,int j){ if (i==j) return 0;//长度为1的情况 int &v=f[i][j]; //v就是f[i][j] if (v!=-1) return v; "该位置被处理过，就不再处理了，记忆化的体现" v=INF; for (int k=i;k<j;k++) v=min(v,dp(i,k)+dp(k+1,j)+s[j]-s[i-1]); return v; }int main() { int n; read(n); for (int i=1;i<=n;i++) read(s[i]),s[i]+=s[i-1]; memset(f,-1,sizeof f); printf("%d",dp(1,n)); return 0;}