网站膜拜销售/提高关键词排名的软文案例

题目大意：

给一个由，(，)，[，]组成的字符串，其中()，[]可以匹配，求最大匹配数

题解：
区间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 10000
string 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;
}