区间DP(基础＋提高)

1.区间dp的定义

在区间上进行动态规划，求解某一个区间的状态的值。主要通过合并小区间的状态进而求出整个大区间状态的值的dp算法。

2.石子合并

题目链接ACwing282.石子合并 - 算法基础课

2.1 思路

2.2 时间复杂度分析

O(n^3) :总共 n*n种状态，每一种状态计算量为n.

2.3 AC代码

#include
using namespace std;
#define int long long
const int N=310;
int n,a[N],s[N],f[N][N];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];//石子质量
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//计算质量和
    for(int len=2;len<=n;len++)//循环区间长度
        for(int i=1;i+len-1<=n;i++)//循环区间左端点
        {
            int j=i+len-1;
            f[i][j]=1e8;
            //循环决策
            for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-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

3.环形石子合并

题目链接1068. 环形石子合并-算法提高课

3.1思路

n个石子形成了一个环形区间，我们可以考虑将环形转化为线形。环形区间有n个石子，需要合并n-1次最后合并为一个。把石子等价为点，把合并等价为两点间连线,题目等价为环形排列的n个点内连n-1条线。而一个环形区间的n个点相邻两个点之间连一条线，可以连n条。 所以环形排列的n个点中有两个点的点对之间没有连线。有序环形排列的n个点中有n种两个点的点 对，对应n种情况，把n种合并情况分别算出， 并分别取最大值和最小值，就是题目所求的答案。

3.2 时间复杂度优化

不过这种做法时间复杂度为O(n^4),需要优化。将环形的n个点依次从1到n标号，合并的点间连线,并将其展开。可以发现，
如果未连线的点对为（i,i+1)，那么这是一条由i到n,1,2一直到i-1的连线，如果把n个点横向排列，并在n个点右边在加上
1,2…n这n个点，也就是等价于从i+1到n+i长度为n-1(两点之间的连线长度为1)的这一个区间。n种情况就分别为长度为2n-1
的区间内n种长度为n-1的区间。求出1到2n内的区间dp，就可以算出n种情况。时间复杂度降低到了O(n^3)。

3.3 AC代码

#include
using namespace std;
#define int long long
const int N=420;//需要构造长度为2*n的数组所以数组要开到大于400
int n,a[N],s[N],f[N][N],g[N][N];//f[N][N]合并最大值,g[N][N]为合并后的最小值。
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];//石子质量
    for(int i=1;i<=n;i++) a[i+n]=a[i];//复制区间,并将该区间加到原区间右边,形成2*n的区间。
    for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];
    memset(g,0x3f,sizeof g);//求最小值预处理成最大值
    for(int i=1;i<=2*n;i++) g[i][i]=0;//预处理初始状态(区间大小为1的得分为0)
    for(int len=2;len<=n;len++)//要求长度为n的区间，所以len最多为n就行
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)//枚举分开点
            {
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
            }
        }
    int mins=1ll<<60,maxn=0;//求最小值预处理成最大值,求最大值预处理成最小值
    for(int i=1;i<=n;i++){
        mins=min(mins,g[i][i+n-1]);
        maxn=max(maxn,f[i][i+n-1]);
    }
    cout<<mins<<endl;
    cout<<maxn<<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

4.能量项链

题目链接320.能量项链-算法提高课

4.1思路

这一题和上面一道一样属于环形dp。
能量珠表示：(x,y) 一个能量珠头标记为x，尾标记为y。
能量珠合并的过程:（a,b）(b,c) ----->（a,c）

4.1.1与环形石子合并的不同之处

环形石子合并中每个石子只有一个参数，而这道题中能量珠有两个参数。合并两个能量珠就像矩阵乘法一样。

4.1.2 状态分析

f[l][r]:从第l个能量珠合并到第r-1个能量珠所释放能量的最大值。其中r表示合并的最后一个珠子的尾标记。
注意:是从l到r-1。
状态转移为:f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j])。两个珠子合并时以左边珠子的尾标记(右边珠子的头标记)k划分。
当i<=n时，a[i]表示第i个珠子的左标记
当i==n+1时，a[i]表示第一个珠子的左标记

4.2 AC代码

#include
using namespace std;
#define int long long
int n,f[210][210],a[210];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) a[i+n]=a[i];
	for(int len=3;len<=n+1;len++)
		for(int i=1;i+len-1<=2*n;i++)
		{
			int j=i+len-1;
			for(int k=i+1;k<j;k++)
				f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
		}
	int maxn=0;
	for(int i=1;i<=n;i++) maxn=max(maxn,f[i][i+n]);
	cout<<maxn;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.加分二叉树

题目链接479. 加分二叉树-算法提高课

5.1 思路

因为一个二叉树的中序遍历中，该二叉树的子树的中序遍历也是连续的一段子序列，所以我们可以想到用区间dp来处理这道题。
状态：f[l][r],g[l][r]。
f[l][r]:

g[l][r]:表示中序遍历是[l…r]这一段区间的二叉树的得分的最大值所对应根节点的编号。
题目要求前序遍历的字典序最小，因为前序遍历先枚举一个树的根节点，所以我们可以在区间最大得分相同的情况下，取根节点编号最小的。

5.2 时间复杂度分析

O(n^3) :总共 n*n种状态，每一种状态计算量为n.

5.3AC代码

#include
using namespace std;
#define int long long
int n,f[33][33],g[33][33],w[33];
void dfs(int l,int r)//前序遍历
{
    if(l>r) return;
    int k=g[l][r];
    cout<<k<<" ";
    dfs(l,k-1);
    dfs(k+1,r);
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];//每个节点的分数
    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            if(len==1) f[i][j]=w[i],g[i][j]=i;
            else {
                for(int k=i;k<=j;k++)
                {
                    int left=k==i?1:f[i][k-1];//左子树为空
                    int right=k==j?1:f[k+1][j];//右子树为空
                    int score=left*right+w[k];
                    if(score>f[i][j])//得分最大所对应的二叉树的根节点编号最小，即前序遍历字典序最小。
                    {
                        g[i][j]=k;//记录根节点的编号
                        f[i][j]=score;
                    }
                }
            }
        }
    cout<<f[1][n]<<endl;
    dfs(1,n);
    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