首页 > 代码库 > 初学DP（1） 黑书中的《括号序列》
初学DP（1） 黑书中的《括号序列》
题目：括号序列
定义如下规则序列（字符串）：
1.空序列是规则序列；
2.如果S是规则序列，那么(S)和[S]也是规则序列；
3.如果A和B都是规则序列，那么AB也是规则序列；
例如，下面的字符串都是规则序列：
(), [], (()), ([]), ()[()];
而这几个就不是规则序列：
(, [, )(, ([];
现在给出一些有‘(‘,‘)‘,‘[‘,‘]‘构成的序列，请添加少量的括号，得到一个规则的序列。
分析：
用s[i],s[j]表示字符串S的第i个字符和第j个字符,i<j，用ans[i][j]表示从第i个字符到第j个字符最少需要添加的括号数；
如果s[i]=‘(‘,s[j]=‘)‘或s[i]=‘[‘,s[j]=‘]‘，那么ans[i][j]=min(ans[i+1][j-1],ans[i][j])；
如果s[i]=‘(‘,s[j]！=‘)‘或s[i]=‘[‘,s[j]！=‘]‘，那么ans[i][j]=min(ans[i+1][j]+1,ans[i][j])；
如果s[i]！=‘(‘,s[j]=‘)‘或s[i]！=‘[‘,s[j]=‘]‘，那么ans[i][j]=min(ans[i][j-1]+1,ans[i][j]);
根据这个我们有如下递推关系：
int bracket(int i,int j){
if (i>j) return 0;
else if (i==j) return 1;
int answer = inf;
if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) answer = min(answer,bracket(i+1,j-1));
else if (s[i]=='(' || s[i]=='[') answer = min(answer,bracket(i+1,j)+1);
else if (s[j]==')' || s[j]==']') answer = min(answer,bracket(i,j-1)+1);
for (int k=i;k<j;k++) answer = min(answer,bracket(i,k)+bracket(k+1,j));
return answer;
}我们发现上面的递归重复计算了好多，下面对于 bracket[0,3]进行说明
我们发现bracket[0,1]以及bracket[2,3]有重复操作，因此如果我们递归求bracket[0,len-1]中len超过100的话，重复操作非常大，很浪费时间；为此我们可以采取先计算出最低层的bracket，对于更高的bracket可以直接使用较低的bracket，这就是自底向下的递推；
参考代码：
#include <iostream>
#include <string.h>
using namespace std;
#define MAX 0xffffff
int main(){
int dp[105][105];
char s[105];
while (cin>>s){
int n=strlen(s);
for (int i=0;i<n;i++){
dp[i][i-1]=0;
dp[i][i]=1;
}
for (int k=1;k<n;k++){ //表示i跟j之间的距离
for (int i=0;i<n-k;i++){
int j=i+k;
dp[i][j]=MAX;
if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){
dp[i][j]=dp[i+1][j-1];
}
for (int p=i;p<j;p++){
if (dp[i][j]>dp[i][p]+dp[p+1][j]){
dp[i][j]=dp[i][p]+dp[p+1][j];
}
}
}
}
cout<<dp[0][n-1]<<endl;
}
return 0;
}poj 1141 http://poj.org/problem?id=1141
题目意思和上面一样，只是题目要你求出这个规则序列，为此我们只需要记录需要插入的位置，当我们需要输出时，采用递推的方式，对于从s[i]到s[j]的序列,如果pos[i][j]=-1则说明s[i]和s[j]括号匹配，我们可以先输出s[i],再继续考虑s[i+1]到s[j-1]的序列，最后输出s[j]，如果pos[i][j]不等于-1则说明s[i]和s[j]不匹配，我们就需要对s[i]进行匹配，输出匹配后，我们再继续考虑s[i+1]到s[j]的序列；
#include <iostream>
#include <string.h>
using namespace std;
#define inf 0xffffff
int dp[105][105];
int pos[105][105];
char s[105];
void show(int i,int j){
if (i>j)
return;
if (i==j){
if(s[i]=='('||s[i]==')')
cout<<"()";
else
cout<<"[]";
}
else{
if (pos[i][j]==-1){
cout<<s[i];
show(i+1,j-1);
cout<<s[j];
}
else{
show(i,pos[i][j]);
show(pos[i][j]+1,j);
}
}
}
int main(){
cin>>s;
int n=strlen(s);
for (int i=0;i<n;i++){
dp[i][i-1]=0;
dp[i][i]=1;
}
for (int k=1;k<n;k++){ //表示i跟j之间的距离
for (int i=0;i<n-k;i++){
int j=i+k;
dp[i][j]=inf;
if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){
pos[i][j]=-1;
dp[i][j]=dp[i+1][j-1];
}
for (int p=i;p<j;p++){
if (dp[i][j]>dp[i][p]+dp[p+1][j]){
pos[i][j]=p;
dp[i][j]=dp[i][p]+dp[p+1][j];
}
}
}
}
show(0,n-1);
cout<<endl;
return 0;
}初学DP（1） 黑书中的《括号序列》
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。