区间DP是DP中比较基础的一种，从名字上来说，就是在一个区间中做动态规划。要先理解区间DP，首先要引入区间DP的三个概念：

起点（左端点）

终点（右端点）

分界点

    我们知道，DP一般用来求最值或求和，所以我们通常用$f[l][r]$来表示从左端点l到右端点r的最大、最小或总和值。我们知道，DP一般用来求最值或求和。当然，我

们还可以根据需要增加维度。分界点我们一般用k表示，模拟小区间转移为大区间的过程。所以，区间DP的一般形式是这样的（C++）：

for (int l=1;l<=n;l++)
{
    for (int r=1;r<=n;r++)
    {
        for (int k=l;k<r;k++)
        {
            #code#;
        }
    }
}

    比如说，洛谷上有这样一道题：

Luogu P1043

这就是一道典型的区间DP，首先要破环为链，然后就做区间DP就好了。代码如下（C++）：

#include <bits/stdc++.h>
#define MAXN 110
using namespace std;
int s[MAXN];
int f_x[MAXN][MAXN][10];
int f_n[MAXN][MAXN][10];
int n,m;
int mo(int x)
{
    return ((x%10)+10)%10;
}
void input()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i+n]=s[i];
    }
    for (int i=1;i<=2*n;i++)
    s[i]+=s[i-1];
}
void init()
{
    for (int i=1;i<=2*n;i++)
    for (int j=i;j<=2*n;j++)
    {
        f_x[i][j][1]=mo(s[j]-s[i-1]);
        f_n[i][j][1]=f_x[i][j][1];
    }
}
void DP()
{
    for (int i=1;i<=2*n;i++)
    for (int j=i;j<=2*n;j++)
    for (int k=2;k<=9;k++)
    f_n[i][j][k]=INT_MAX;
    for (int i=2;i<=m;i++)
    {
        for (int l=1;l<=2*n;l++)
        {
            for (int r=l+i-1;r<=2*n;r++)
            {
                for (int k=l+i-2;k<r;k++)
                {
                    f_x[l][r][i]=max(f_x[l][r][i],f_x[l][k][i-1]*mo(s[r]-s[k]));
                    f_n[l][r][i]=min(f_n[l][r][i],f_n[l][k][i-1]*mo(s[r]-s[k]));
                }
            }
        }
    }
}
void output()
{
    int ans_n=INT_MAX;
    int ans_x=0;
    for (int i=1;i<=n;i++)
    {
        ans_x=max(ans_x,f_x[i][i+n-1][m]);
        ans_n=min(ans_n,f_n[i][i+n-1][m]);
    }
    cout<<ans_n<<endl<<ans_x<<endl;
}
int main()
{
    input();
    init();
    DP();
    output();
    return 0;
}

这道题的注意事项有：要注意k的范围及f数组的初始值。
    好，区间DP我们就说到这里。