【算法与数据结构】——区间DP

野性酷女 2022-09-03 10:17 167阅读 0赞

## 介绍 ##

区间DP属于线性DP的一种，以区间长度作为DP的阶段，以区间的左右端点作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。阶段（长度），状态（左右端点），决策三者按照由外到内的顺序构成3层循环。  
接下来介绍一个典型问题。

## 石子合并问题 ##

有N堆石子排成一排，每堆石子有一定的数量。先要将2堆石子合并成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后称为一堆。求总的代价最小值。  
**问题分析**：  
1.求某个区间的最优解\[1,n\];  
2.大的区间由包含于它的小区间组成（转移而来）；  
3.满足DP的三个基本条件。  
**状态**  
通用状态的定义：DP\[i\]\[j\]从i到j区间的最优解。  
目标状态的表示：DP\[1,n\]  
阶段的划分：区间长度  
决策（状态转移）  
dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i\]\[k\]+dp\[k+1\]\[j\]+w\[i\]\[j\])  
w\[i\]\[j\]是从i到j区间总的石子重量，可以用前缀和求得。  
\*\*区间DP：\*\*小结：在区间上动态规划，具体的说就是，现在小区间进行DP得到小区间的最优解，然后通过合并小区间的最优解，进而求出大区间的最优解。  
阶段的划分：区间长度  
状态的表示：枚举起点（不同起点，不同状态）  
决策的实现：枚举分割点

区间DP的状态设计相对简单，基本大部分问题都适用。  
DP\[i\]\[j\]代表区间\[i,j\]上的最优解。  
状态转移一定是从区间长度短的状态到区间长度长的状态。  
**模板**  
迭代

for(int len=2;len<=n;len++)		//区间长度
    {	
    	for(int i = 1;i<=n;i++)			//枚举起点
    	{
    		int j=i+len-1;					//计算区间终点
    		if(j>n) break;					//越界结束
    		for(int k = i;k<j;k++)			//枚举分割点，构造状态转移方程
    		{
    			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j];
    		}
    	}
    }

记忆化DFS：

int MINdfs(int l,int r)		//推荐记忆化DFS的实现方式，更简单，不容易出错。
    {
    	int &D = dp[l][r];	//引用D就代表dp[l][r],这个方法可以简化代码
    	//inf是自定义的整型最大值
    	if(D!=inf)return D;	//如果已经搜索过就返回这个值，记忆化搜索的重点
    	if(l == r) return D=0;	//如果l==r,无需合并，所以返回0
    	for(int i = l;i<r;i++)	//枚举所有可行的区间分割方案
    		D=min(D,MINdfs(l,i)+MINdfs(i+1,r)+sum[r]-sum[l-1];
    	return D;	
    }

## 回文 ##

题目[Cheapest Palindrome][]  
题意：给出一个字符串，以及添加或删除部分字符的成本，求将字符串变为回文串所需的最小成本。只能添加或删除给出成本的字符。  
思路：区间DP，用dp\[i\]\[j\]表示将字符串下标i到j的子串变为回文串所需的最小成本，无非是在左端删除一个字符或者在右端添加一个字符。两种情况，如果s\[i\]等于s\[j\]就不需要进行操作，dp\[i\]\[j\] = dp\[i+1\]\[j-1\],如果s\[i\]不等于s\[j\]，要么在右端添加字符s\[i\]要么在左端删除字符s\[i\]，两种情况取最小值dp\[i\]\[j\] = min(dp\[i+1\]\[j\]+w\[str\[i\]-‘a’\],dp\[i\]\[j-1\]+w\[str\[j\]-‘a’\])  
AC代码：

/* **Author:skj **Time:8-6 **Function:区间DP poj3280 */
    //#include <bits/stdc++.h>
    #include <string>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxm = 2002;
    
    int dp[maxm][maxm];
    int w[27];
    int main()
    { 
    	freopen("in.txt","r",stdin);
    	freopen("out.txt","w",stdout);
    	cin.sync_with_stdio(0);
    	cin.tie(0);
        string str;
        int n,m;
        cin >> n >> m;
        cin >> str;
        while(n--)
        { 
            char c;
            int a,b;
            cin >> c;
            cin >> a >> b;
            w[c-'a'] = min(a,b);//因为对于一个字符的操作不是删除就是添加，而且不需要知道最终的字符串，所以到底是删除了字符还是添加了字符就不需要知道的很确切，这里只需要保存一个最小值就可以了
        }
        for(int i = m-1;i >= 0;i--)//从字符串最右侧开始是为了确保能正确遍历dp数组
        { 
            for(int j = i+1;j < m;j++)
            { 
                if(str[i]==str[j])
                { 
                    dp[i][j] = dp[i+1][j-1];
                }
                else
                { 
                    dp[i][j] = min(dp[i+1][j]+w[str[i]-'a'],dp[i][j-1]+w[str[j]-'a']);
                }
            }
        }
        cout << dp[0][m-1] << endl;
        return 0;
    }

## 括号匹配 ##

题目地址[POJ 2955 Brackets][]  
题意：正则括号序列，就是从语法上来说合法的括号序列,类似(),()\[(())\]都可以，但是\[(\])不可以，给出一个序列，问他的子序列中最长的正则括号序列长度  
思路：区间DP，与回文字符串思路基本一样，但是不同的是\[((\[\]))\]这种情况，需要处理，在代码中说明。  
AC代码：

/* **Author:skj **Time:8-7 **Function:poj 2955 区间DP 括号匹配 */
    //#include <bits/stdc++.h>
    #include <iostream>
    #include <string>
    #include <cstring>
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxn = 101;
    int dp[maxn][maxn];
    bool judge(char c1,char c2)
    { 
        if(c1 == '('&&c2==')')
        { 
            return true;
        }
        else if(c1=='['&&c2==']')
        { 
            return true;
        }
        else if(c1=='{'&&c2=='}')
        { 
            return true;
        }
        return false;
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        cin.sync_with_stdio(0);
    	cin.tie(0);
    	string s;
    	cin >> s;
    	while(s!="end")
        { 
            int l = s.size();
            for(int i = l-1;i>=0;i--)
            { 
                for(int j = i+1;j<l;j++)
                { 
                    if(judge(s[i],s[j]))
                    { 
                        dp[i][j] = dp[i+1][j-1]+2;
                    }
                    for(int k = i;k<j;k++)//处理[()]([()])这种情况，需要遍历所有子问题之和取最大值。
                    { 
                        dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
                    }
                }
            }
            cout << dp[0][l-1] << endl;
            memset(dp,0,sizeof(dp));
            cin >> s;
        }
        return 0;
    }

## 猴子派对 ##

题目地址【[HDU 3506 Monkey Party][]】  
题意：N只猴子坐成环，都不认识对方，森林之王每次介绍两只猴子A和B，A和B相邻，A认识的每只猴子都将认识B已经认识的每只猴子，介绍的总时间是A和B已经认识的所有猴子交友时间的总和。每只猴子都认识自己。求最短的介绍时间。  
思路：跟合并石子的题目有点像，属于环型的石子合并。  
属于区间DP，n只猴子坐在一个圈里，是一个环，对于包含n个元素的环型，可以将前n-1个元素一次复制到第n个元素后面，将环型转化为直线型。  
a1，a2，··· a n a\_n an,a1··· a n − 1 a\_\{n-1\} an−1,然后以长度作为阶段，以序列的开始和结束下标作为状态的维度，通过不同的情况执行不同的决策。  
状态表示：dp\[i\]\[j\]表示\[i,j\]区间猴子相互认识的最少时间。枚举每一个位置k，求两个子问题之和的最小值。  
状态转移方程：dp\[i\]\[j\]=min(dp\[i\]\[k\]+dp\[k+1\]\[j\]+sum(i,j))。  
最后从规模是n的最优值中找出最小值即可。  
该算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3),数据范围 1 ≤ n ≤ 1000 1\\le n \\le1000 1≤n≤1000,超时，考虑采用四边不等式优化。  
求解dp\[i\]\[j\]时，需要枚举位置k=i,···，j-1,用s\[i\]\[j\]记录dp\[i\]\[j\]取得最小值的位置k。利用四边形不等式优化后，k的枚举范围变为s\[i\]\[j-1\]~s\[i+1\]\[j\],枚举范围小了很多。

#include<bits/stdc++.h>
    using namespace std;
    int a[2010];//存前缀和
    int dp[2010][2010];
    int s[2010][2010];//记录最优分割点
    int inf=0x3f3f3f3f;
    
    int main(){ 
    	int n;
    	while(cin>>n){ 
    		for(int i=1;i<=n;i++){ 
    			cin>>a[i];
    			a[i+n]=a[i];
    		}
    		memset(dp,inf,sizeof(dp));
    		for(int i=1;i<=n*2;i++) a[i]+=a[i-1];
    		for(int i=1;i<=n*2;i++){ 
    			dp[i][i]=0;
    			s[i][i]=i;
    		}
    		for(int len=1;len<n;len++){ 
    			for(int i=1;i<=n;i++){ 
    				int j=i+len;
    				for(int k=s[i][j-1];k<=s[i+1][j];k++){ 
    					if(dp[i][k]+dp[k+1][j]+a[j]-a[i-1]<dp[i][j]){ 
    						dp[i][j]=dp[i][k]+dp[k+1][j]+a[j]-a[i-1];
    						s[i][j]=k;
    					}
    				}
    			}
    		}
    		int m=1e9;
    		for(int i=1;i<=n;i++){ 
    			m=min(m,dp[i][i+n-1]);
    		}
    		cout<<m<<endl;
    	}
    }

[Cheapest Palindrome]: http://poj.org/problem?id=3280
[POJ 2955 Brackets]: http://poj.org/problem?id=2955
[HDU 3506 Monkey Party]: https://acm.hdu.edu.cn/showproblem.php?pid=3506