括号序列问题 uva 1626 poj 1141【区间dp】
首先考虑下面的问题：Code[VS] 3657
我们用以下规则定义一个合法的括号序列：
（1）空序列是合法的
（2）假如S是一个合法的序列，则 (S) 和[S]都是合法的
（3）假如A 和 B 都是合法的，那么AB和BA也是合法的
例如以下是合法的括号序列：
(), [], (()), ([]), ()[], ()[()]
以下是不合法括号序列的：
(, [, ], )(, ([]), ([()
现在给定一些由'(', ')', '[', ，']'构成的序列 ，请添加尽量少的括号，得到一个合法的括号序列。
输入包括号序列S。含最多100个字符（四种字符： '(', ')', '[' and ']') ，都放在一行，中间没有其他多余字符。
使括号序列S成为合法序列需要添加最少的括号数量。
样例输入 Sample Input
([()
样例输出 Sample Output
2
这是LRJ黑书上讲动态规划的第一道例题，我觉得不算简单>_<.，但让我明白了动态规划的两种动机：记忆化搜索和自底向上的递推。先说这道题的理解，黑书上设SiSi+1...Sj最少需要添加d[i,j]个括号。当S是'(S)'或'[S]'形式是很好理解，由于两端是对称的，那么我可以递归考虑里面的：d[i,j]=d[i+1,j-1]。当S是'(S'、'[S'、'S)'、'S]'等类似前面的道理，只不过考虑的分别是d[i,j]=d[i+1,j],d[i,j]=d[i,j-1]。其实让我迷惑的是最后还要把S分成两段Si....Sk,Sk+1...Sj分别求解再相加。后来看了别人博客的解释才明白些。因为S就可以只看成两类，两段匹配的和不匹配的，匹配的直接递归，不匹配的就分成两部分再求解。
所以针对上面的问题，就有了两种dp写法。dp[i][j]表示i、j为开头结尾时需要添加的括号数。
记忆化搜索：参考代码如下。黑书里面写的有我注释那那部分，但是按照上面的分析，其实直接分成dp[i][j]=dp[i+1][j-1]和dp[i][j]=dp[i][k]+dp[k+1][j]就可以了。但是我觉得那部分代码对我理解递归还是个很有帮助的，而且不注释好像更快些。Recursive is amazing！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = ;
int dp[MAXN][MAXN];
char s[MAXN]; int dfs(int i, int j)
{
if (dp[i][j] != -) return dp[i][j];
if (i > j) return ;
if (i == j) return ;
int ans = 1e9;
if ((s[i] == '('&&s[j] == ')') || (s[i] == '['&&s[j] == ']'))
ans = min(ans, dfs(i + , j - ));
/*else if (s[i] == '(' || s[i] == '[')
ans = min(ans, dfs(i + 1, j) + 1);
else if (s[j] == ')' || s[j] == ']')
ans = min(ans, dfs(i, j - 1) + 1);*/
for (int k = i; k < j; k++)
ans = min(ans, dfs(i, k) + dfs(k + , j));
return dp[i][j] = ans;
} int main()
{
while (scanf("%s",s)==)
{
int len = strlen(s);
memset(dp, -, sizeof(dp));
printf("%d\n", dfs(, len - ));
}
}
自底向上的递推：其实看起来代码和上面的差不多。也是一样，去掉注释竟然会快些。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = ;
int dp[MAXN][MAXN];
char s[MAXN]; int main()
{
while (scanf("%s",s)==)
{
int len = strlen(s);
for (int i = ; i < len; i++) {
dp[i][i] = , dp[i][i - ] = ;
}
for (int p = ; p < len; p++)//p指的是i、j之间的距离
{
for (int i = ; i + p < len; i++)
{
int j = i + p;
dp[i][j] = 1e9;
if ((s[i] == '('&&s[j] == ')') || (s[i] == '['&&s[j] == ']'))
dp[i][j] = dp[i + ][j - ];
/* else if (s[i] == '(' || s[i] == '[')
dp[i][j] = min(dp[i][j], dp[i + 1][j])+1;
else if (s[j] == ')' || s[j] == ']')
dp[i][j] = min(dp[i][j], dp[i][j - 1])+1; */
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+][j]);
}
}
printf("%d\n", dp[][len - ]);
}
return ;
}
下面的UVa 1626 poj 1141就是比上面的题多了个输出结果，这俩题一样，就是输入输出要求有点差别而已。需要特别注意的是，这两道题输入中都有空格，所以只能用gets()函数，我用scanf("%s")WA到死。。。（也没见题中说由空格啊！有空格还对吗？难道空格是在字符串开头？）
其实一看见让输出我是很懵逼的，这怎么输出。能求出最少添加数我就很开心了。下面说说自己的理解，别人的方法是递归输出。既然是递归输出，就先考虑一下边间，显然i>j时直接return.i==j时，是'('或')'输出'()'否则输出'[]'，当i!=j时，若i,j两端点正好匹配，那就先输出左端点再递归输出i+1,j-1部分最后输出又端点，若是剩下的其他情况就像上面一样分成两部分判断继续递归。这里分成两部分后应该在哪里分开递归？自然是在更新dp[i][j]=dp[i][k]+dp[k+1][j]的地方，网上有人在dp时添加了另外一个数组记录这个位置，也有人没有添加，而是递归输出结果的时候再判断，我这里选择了第二种，代码看起来简洁些。
自底向上递推：为了方便把端点匹配的情况写成了一个函数。有一个点就是注释里的dp[i][j]==dp[i+1][j-1]不能少，否则会WA！感觉应该是虽然有可能i,j匹配，但这不是原序列中i、j对应的匹配，因为这时候是在递归，所以不加上会WA。估计我比赛的时候不会注意到这种细节。。。。但另开个数组记录就不用考虑了。
UVa 1626
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=;
int dp[MAXN][MAXN];
char s[MAXN]; bool Judge(int i,int j)
{
if(s[i]=='('&&s[j]==')') return ;
if(s[i]=='['&&s[j]==']') return ;
return ;
} void Print(int i,int j)
{
if(i>j) return;
if(i==j){
if(s[i]=='('||s[j]==')') printf("()");
else printf("[]");
return;
}else if(Judge(i,j)&&dp[i][j]==dp[i+][j-]){//后面的判断条件不能省略
printf("%c",s[i]);
Print(i+,j-);
printf("%c",s[j]);
return;
}else for(int k=i;k<j;k++)
if(dp[i][j]==dp[i][k]+dp[k+][j]){
Print(i,k);
Print(k+,j);
return;
}
} int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
gets(s);
gets(s);
int len=strlen(s);
memset(dp,,sizeof(dp));
for(int i=;i<len;i++){
dp[i][i]=,dp[i][i-]=;
}
for(int p=;p<len;p++)
{
for(int i=;i+p<len;i++)
{
int j=i+p;
dp[i][j]=1e9;
if(Judge(i,j))
dp[i][j]=dp[i+][j-];
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
Print(,len-);
printf("\n");
if(T)
printf("\n");
}
return ;
}
附带一个用flag[]数组标记的写法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=;
int dp[MAXN][MAXN],flag[MAXN][MAXN];
char s[MAXN]; bool Judge(int i,int j)
{
if(s[i]=='('&&s[j]==')') return ;
if(s[i]=='['&&s[j]==']') return ;
return ;
} void Print(int i,int j)
{
if(i>j) return;
if(i==j){
if(s[i]=='('||s[j]==')') printf("()");
else printf("[]");
return;
}else if(flag[i][j]==-){
printf("%c",s[i]);
Print(i+,j-);
printf("%c",s[j]);
return;
}else {
Print(i,flag[i][j]);
Print(flag[i][j]+,j);
}
} int main()
{
int T;
scanf("%d",&T);
getchar();
while(T--)
{
gets(s);
gets(s);
int len=strlen(s);
memset(dp,,sizeof(dp));
for(int i=;i<len;i++){
dp[i][i]=,dp[i][i-]=;
}
for(int p=;p<len;p++)
{
for(int i=;i+p<len;i++)
{
int j=i+p;
dp[i][j]=1e9;
if(Judge(i,j)){
dp[i][j]=dp[i+][j-];
flag[i][j]=-;
}
for(int k=i;k<j;k++){
if(dp[i][j]>dp[i][k]+dp[k+][j]){
dp[i][j]=dp[i][k]+dp[k+][j];
flag[i][j]=k;
}
}
}
}
Print(,len-);
printf("\n");
if(T)
printf("\n");
}
return ;
}
UVa 1626 用flag[]标记
poj 1141类似:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = ;
int dp[MAXN][MAXN];
char s[MAXN]; bool Judge(int i, int j)
{
if (s[i] == '('&&s[j] == ')') return true;
if (s[i] == '['&&s[j] == ']') return true;
return false;
} void Print(int l, int r)
{
if (l > r) return;
if (l == r) {
if (s[l] == '(' || s[r] == ')')
printf("()");
else printf("[]");
return;
}
else if (Judge(l, r) && dp[l][r] == dp[l + ][r - ]) {
printf("%c", s[l]);
Print(l + , r - );
printf("%c", s[r]);
}else for(int k=l;k<r;k++)
if (dp[l][r] == dp[l][k] + dp[k + ][r]) {
Print(l, k);
Print(k + , r);
break;
}
} int main()
{
while (gets(s))
{
int len = strlen(s);
memset(dp, , sizeof(dp));
for (int i = ; i < len; i++) {
dp[i][i - ] = , dp[i][i] = ;
}
for (int p = ; p < len; p++)
{
for (int i = ; i < len - p; i++) {
int j = i + p;
dp[i][j] = 1e9;
if ((s[i] == '('&&s[j] == ')') || (s[i] == '['&&s[j] == ']'))
dp[i][j] = dp[i + ][j - ];
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + ][j]);
}
}
Print(, len - );
printf("\n");
}
return ;
}
自底向上递推poj1141
记忆化搜索也是类似的方法，比递推满了好多倍。。用flag[]数组标记比较好，不标记不知道怎么弄>_<。而且要像上面一样令int ans=1e9,最后再返回dp[i][j]=ans,直接令dp[i][j]=1e9会出错。。。先不深究了，这题写了一天。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = ;
int dp[MAXN][MAXN],flag[MAXN][MAXN];
char s[MAXN]; bool Judge(int i, int j)
{
if (s[i] == '('&&s[j] == ')') return ;
if (s[i] == '['&&s[j] == ']') return ;
return ;
} int dfs(int i, int j)
{
if (dp[i][j] != -) return dp[i][j];
if (i > j) return ;
if (i == j) return ;
int ans = 1e9;
if (Judge(i,j)) {
ans = min(ans, dfs(i + , j - ));
flag[i][j] = -;
}
for (int k = i; k < j; k++) {
if (ans > dfs(i, k) + dfs(k + , j)) {
ans = dfs(i, k) + dfs(k + , j);
flag[i][j] = k;
}
}
return dp[i][j] = ans;
} void Print(int i, int j)
{
if (i>j) return;
if (i == j) {
if (s[i] == '(' || s[j] == ')') printf("()");
else printf("[]");
return;
}
else if (flag[i][j] == -) {
printf("%c", s[i]);
Print(i + , j - );
printf("%c", s[j]);
return;
}
else {
Print(i, flag[i][j]);
Print(flag[i][j] + , j);
}
} int main()
{
int T;
scanf("%d", &T);
getchar();
while (T--)
{
gets(s);
gets(s);
int len = strlen(s);
memset(dp, -, sizeof(dp));
dfs(, len - );
Print(, len - );
printf("\n");
if (T)
printf("\n");
}
return ;
}
记忆化搜索Uva 1626
poj 1141的完全类似。。。
最新文章
- 如何写复杂的SQL
- XNA游戏编程等
- phpcms V9 栏目管理
- 关于UIView的AutoresizingMask属性的研究
- xampp 端口冲突
- MJRefresh简单处理
- MapReduce编程系列 — 6：多表关联
- Apache与Tomcat区别联系
- C语言编程时常犯十八个错误
- 必须熟悉的vim快捷键操作
- dotnet Core 调用HTTP接口，系统大量CLOSE_WAIT连接问题的分析，尚未解决。
- 用java编写一个微博登陆页面
- 张金禹 C语言--第0次作业
- 从零开始系列之vue全家桶（6）实战前的设计
- Mad libs
- Focal Loss
- Benchmarking Zeebe: An Intro to How Zeebe Scales Horizontally and How We Measure It
- centos 7 hadoop的安装和使用
- sql随机查询数据order by newid()
- 《LeetBook》leetcode题解(17):Letter Combinations of a Phone Number[M]