动态规划之区间DP详解

什么是区间DP？

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

典型例题一：石子合并

1.1 题目：

题目链接

1.2 分析：

1.2.1 状态表示：
f[l,r]表示把从L到R合并成一堆的最小代价。
1.2.2 状态转移：

1. 先把区间[L,R]切分成两部分[L,K], [K+1，R], k是切分点；
2. 再把两部分[L,R]和[k+1，R]合并在一起。（利用前缀和求区间和）

转移：
f[L,k] + f[k+1,R] + s[R] - s[L-1] ——>f[L,R]
计算：
f[L,R]=min(f[L,R] , f[L,k] + f[k+1,R] + s[R] - s[L-1])

1.2.3 边界情况：
f[i,i]=0(合并每堆石子的代价为0），其余为正无穷。

1.3 完整代码：

// 算法：区间DP
// 时间：2022.07.13 20点06分
#include
#include
using namespace std;

const int N=310;
int n;//石子堆数
int s[N];//记录前缀和 用来求合并时候花费的代价
int f[N][N];//f[i][j]表示把从l到r合并成一堆的最小代价
int main ()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    //求前缀和
    for(int i=1;i<=n;i++) s[i]+=s[i-1];
    
    for(int len=2;len<=n;len++)//阶段：枚举区间长度
        for(int i=1;i+len-1<=n;i++)//状态：枚举区间起点
            {
                int l=i,r=i+len-1;//区间的左右端点
                f[l][r]=1e9;
                for(int k=l;k<r;k++)//决策：枚举分割点
                //枚举最后一次合并的分界点
                    f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
    cout<<f[1][n]<<endl;
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

典型例题二：环形石子合并

2.1 题目：

2.2 分析：

这个问题只是将例题一的链式石子合并转换为环形，那么我们首先可以想到将环形问题转换为链式。对于环上的每一条边进行切割将其变为链式，所以只需要再多加一层循环即可。

核心代码：

for(int j=1;j<=n;j++)//枚举环形的缺口
    for(int len=2;len<=n;len++)//阶段：枚举区间长度
        for(int i=1;i+len-1<=n;i++)//状态：枚举区间起点
            {
                int l=i,r=i+len-1;//区间的左右端点
                f[l][r]=1e9;
                for(int k=l;k<r;k++)//决策：枚举分割点
                //枚举最后一次合并的分界点
                    f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
1
2
3
4
5
6
7
8
9
10

但是显而易见时间复杂度是O（n⁴)，所以会TLE,那么如何进行优化呢？？
这里提供一种常见的环形问题转换为链式的一种方法：
复制一遍数组，转化为长度为2N的链形数组。

核心代码：

//链形石子合并模板
for(int len=2;len<=n;len++)//阶段：枚举区间长度
    for(int l=1;l+len-1<=2*n;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]+s[r]-s[l-1]);
    }
1
2
3
4
5
6
7
8

2.3 完整代码:

#include
using namespace std;

const int N=110,INF=0x3f3f3f3f;
int n;
int a[N];
int s[N];//记录前缀和
int f[N][N];//f[l][r]表示把从l到r合并成一堆的得分的最小值
int g[N][N];//g[l][r]表示把从l到r合并成一堆的得分的最大值
int main ()
{
    memset(f,INF,sizeof f);
    memset(g,-INF,sizeof g);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];//复制一遍区间
    }
    for(int i=1;i<=2*n;i++){
        s[i]=s[i-1]+a[i];//前缀和
        g[i][i]=0,f[i][i]=0;
    }
    //DP
    for(int len=2;len<=n;len++)
        for(int l=1;l+len-1<=2*n;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]+s[r]-s[l-1]);
                g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
            }
        }
    //输出
    int minv=INF,maxv=-INF;
    for(int i=1;i<=n;i++){
        minv=min(minv,f[i][i+n-1]);
        maxv=max(maxv,g[i][i+n-1]);
    }
    cout<<minv<<endl<<maxv<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40