DP学习笔记——区间DP

做了几天水题经过几天的学习，我大致掌握了区间DP明白理论但是不会写代码
下面浅析下区间DP

区间DP是什么

顾名思义，就是在区间上的DP
区间DP实际上是一种线性DP的拓展，它在分阶段划分问题时，与阶段中元素出现的顺序和由前一阶段的那些元素合并而来的有很大联系。（出自《信息学奥赛一本通（提高篇）》）
我认为区间DP就是将问题分开成小区间，求完最优解，再把它合并起来，就得到全部的最优解了。

区间DP有哪些经典题目

P1880 [NOI1995] 石子合并
一道非常经典的区间DP题目，将大区间分成若干个小区间合并，最后合并完求最优解

  for(int l=1;l<2*n;++l)
    {
        for(int r=l+1;r<=2*n&&r<=l+n-1;++r)
        {
            for(int k=l;k

for(int l=2;l<=n;++l)
	{
		for(int i=0;l+i-1

for(int i=2*n;i>=1;--i)
	{
		for(int j=i;j<=2*n;++j)
		{
			for(int k=i;k<=j;++k)
			{
				f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+a[i-1]*a[k]*a[j+1]);
			}
		if(j-i+1==n-1) ans=max(ans,f[i][j]);
		}
	}