poj 2955 Brackets(區間DP求最長匹配子串)

poj 2955 Brackets(區間DP求最長匹配子串)

思路：假設要求區間[i,j]的最長匹配字串，它必然可以從[i,j-1]轉移而來，有可能是s[j]與s[i]發生“關系”（匹配或不匹配），一直到s[j-1],若不發生“關系”，即s[j]跟自己發生“關系”，用for循環枚舉所有的可能，取最大值。

代碼：

#include
#include
#include
using namespace std;

char s[105];
int dp[105][105];//代表[i,j]區間的最長匹配子串

int check(int i,int j)
{
    if(s[i]=='('&&s[j]==')')
        return 1;
    if(s[i]=='['&&s[j]==']')
        return 1;
    return 0;
}

int main()
{
    while(scanf("%s",s)&&strcmp(s,"end")!=0)
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        for(int i=0;i