本文主要是介绍poj2955，开始学习区间dp了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
— 题目大意：给出一个括号序列，求出其中匹配的括号数
((())) 6
()()() 6
— ([]]) 4
— )[)( 0
([][][)
6
— 第一步：确定状态
—dp[i][j]表示a[i]……a[j]的串中，有多少个已经匹配的括号
—第二步：确定状态转移方程
— 如果 a[i] 与 a[k] 是匹配的
— dp[ i ][j]= max(dp[ i ][j], dp[ i + 1][k - 1] + dp[k + 1][j] + 2)
— （相当于是将 i 到 j 分成 [ xxxxx ] xxxxx 两部分）
— 否则 dp[ i ][j] =max(dp[i][j],dp[ i +1][j])
— （将第一个元素去掉 —— 因为它肯定不能算）
— 边界 dp[ i ][ i ] = 0.
— 如果用递推的话，应该是区间大小由小到大递增作为最外层循环
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int dp[105][105];
char a[105];
bool check(int i,int j)
{if(a[i]=='('&&a[j]==')') return true;if(a[i]=='['&&a[j]==']') return true;return false;
}
int main()
{int i,j,k,l;gets(a);while(a[0]!='e'){memset(dp,0,sizeof(dp));l=strlen(a);for(i=2;i<=l;i++)//枚举区间长度从2到lfor(j=0;j+i-1<l;j++)//枚举起始位置for(k=j+1;k<=j+i-1;k++) //枚举中间的kif(check(j,k))dp[j][j+i-1]=max(dp[j][j+i-1],dp[j+1][k-1]+dp[k+1][j+i-1]+2);elsedp[j][j+i-1]=max(dp[j][j+i-1],dp[j+1][j+i-1]);printf("%d\n",dp[0][l-1]);gets(a);}
}
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[105][105];
char a[105];
int main()
{int i,j,len;gets(a+1);while(a[1]!='e'){a[0]=1;len=strlen(a)-1;memset(dp,0,sizeof(dp));for(i=len-1;i>=1;i--){for(j=i+1;j<=len;j++){dp[i][j]=dp[i+1][j];for(int k=i+1;k<=j;k++){if((a[i]=='('&&a[k]==')')||(a[i]=='['&&a[k]==']')){dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);}}}}printf("%d\n",dp[1][len]);gets(a+1);}return 0;
}
这篇关于poj2955，开始学习区间dp了的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
