所谓区间dp，顾名思义就是在一段区间上的动态规划，从小区间求得解开始向外部延伸的算法；

         1.普遍情况下的核心代码： 

    for(int s=2;s<=n;s++)//枚举终点
    {
        for(int w=s-1;w>0;w--)//枚举起点
        {
            for(int k=w;k<=s;k++)//枚举断点
            {
                dp[w][s]=min(dp[w][s],dp[w][k]+dp[k+1][s]+改变的值);//或者max~看题意。
            }
        }
    }
             在这里起点要从s-1到1倒着推是为了保证先确定小区间的最优值再扩展到大区间上~~别忘了；
         

         2.经典的线式环境下的区间dp

       （1）.sdnu 1045  http://www.acmicpc.sdnu.edu.cn/problem/show/1045（附帐号 heheda11  密码xiaoshibo0536）

                          1045.石子合并1

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 136    Accepted Submission(s): 56

Description

有n堆石子排成一行，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数。

Output

一个整数，表示最小总得分。

Sample Input

5
7 6 5 7 100

Sample Output

175

Source

Unknown 

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[205][205];//dp【s】【w】表示从s到w的最少的费用
int sum[205];//表示前n项和
int n;
void cla()
{
    for(int s=2;s<=n;s++)
    {
        for(int w=s-1;w>0;w--)
        {
            for(int k=w;k<=s;k++)
            {
                dp[w][s]=min(dp[w][s],dp[w][k]+dp[k+1][s]+sum[s]-sum[w-1]);//假设要把这两部分合成那么额外的费用就是从w到s的堆中数量和，即sum[s]-sum[w-1]
            }
        }
    }
}
int main()
{
    cin>>n;
    memset(sum,0,sizeof(sum));//初始化
    memset(dp,0x3f,sizeof(dp));
    for(int s=1;s<=n;s++)
    {
        int a;
        scanf("%d",&a);
        sum[s]=sum[s-1]+a;
        dp[s][s]=0;
    }
    cla();
    printf("%d\n",dp[1][n]);
    return 0;
}

1048.石子合并2

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 126    Accepted Submission(s): 43

Description

有n堆石子排成一圈，每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

Input

第一行一个整数n(1 <= n <= 200)，表示石子堆数； 第二行n个整数a(1 <= a <= 100)，表示每堆石子的个数，这些石子首尾相接排成一圈。

Output

一个整数，表示最小总得分。

Sample Input

5
7 6 5 7 100

Sample Output

175

Source

Unknown

            之前的时候我们是线性的方法~那么环式的我们怎么解决呢~

            很简单，再克隆一个串穿在第n个数据后面，来表面上形成2个串，这样计算的时候就会全部考虑到了。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[2005][2005];//最小的费用
int sum[2005];//前n项和
int m[2005];//数据
int best[2005][2005];
int n;
void cla()
{
	for (int s = 2; s <= 2 * n; s++)//枚举后端
	{
		for (int w = s - 1; w>0 && s - w<n; w--)//枚举前端
		{
			for (int k = best[w][s - 1]; k <= best[w + 1][s]; k++)//枚举断点
			{
				if (dp[w][s]>dp[w][k] + dp[k + 1][s] + sum[s] - sum[w - 1])
				{
					dp[w][s] = dp[w][k] + dp[k + 1][s] + sum[s] - sum[w - 1];
					best[w][s] = k;
				}
			}
		}
	}
}
int main()
{
	cin >> n;
	memset(sum, 0, sizeof(sum));
	memset(dp, 0x3f3f3f, sizeof(dp));
	for (int s = 1; s <= n; s++)
	{
		scanf("%d", &m[s]);
		m[s + n] = m[s];
	}
	for (int s = 1; s <= 2 * n; s++)
	{
		sum[s] = sum[s - 1] + m[s];
		dp[s][s] = 0;
		best[s][s] = s;
	}
	cla();
	int ans = 0x3f3f3f3f;
	for (int s = 1; s <= n; s++)//因为是环形所以要去全部查询一编
	{
		ans = min(ans, dp[s][s + n - 1]);
	}
	cout << ans << endl;
	return 0;
}

                 然后我们在说一下之中填的best函数~~这个里面记录的是best[w][s]是指从w到s的分割的最优的那个断点的位置是哪里~~具体的细节你们可以看一下平行四边形优化法则（http://www.cnblogs.com/jiu0821/p/4493497.html）~~这样的话可以优化成n^2的状态~。