首页 > 代码库 > poj2955：括号匹配，区间dp
poj2955：括号匹配，区间dp
题目大意：
给一个由，(，)，[，]组成的字符串，其中()，[]可以匹配，求最大匹配数
题解：
区间dp：
dp[i][j]表示区间 [i，j]中的最大匹配数
初始状态 dp[i][i+1]=(i,i+1可以匹配)？2：0
状态转移见代码
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000string s;int dp[105][105];int ok(int x,int y){ return (s[x]==‘(‘&&s[y]==‘)‘)||(s[x]==‘[‘&&s[y]==‘]‘);}int main(){ while(cin>>s,s!="end") { memset(dp,0,sizeof(dp)); int n=s.length(); for(int k=1;k<n;k++) { for(int i=0;i+k<n;i++) { if(ok(i,i+k)) { dp[i][i+k]=2+dp[i+1][i+k-1]; //匹配 } for(int j=i;j<i+k;j++) { dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j+1][i+k]); //不匹配 } } } cout<<dp[0][n-1]<<endl; } return 0;}
poj2955：括号匹配，区间dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。