思路:假設要求區間[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