题目类型 DP
题目意思
给出一个最长 100 的括号序列 问最长配对的括号子序列的长度是多少
括号的合法匹配有 () 和 [] 两种
例如 ((())) 最长是 6 而 [((]) 最长是 2
解题方法
记忆化搜索
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[110];
int dp[110][110];
int DFS(int l, int r) {
if(l >= r) return 0; // 肯定没配对
if(r - l == 1) {
if(str[l] == '(' && str[r] == ')') return 2; // 匹配返回2
if(str[l] == '[' && str[r] == ']') return 2;
return 0;
}
if(dp[l][r] != -1) return dp[l][r]; // 如果这段序列之前已经搜索过直接返回
for( int i=l; i<=r; i++ ) {
if(str[l] != '(' && str[l] != '[') dp[l][r] = max(dp[l][r], DFS(l+1, r)); // 如果序列的第一个不是左括号 直接去掉
else { // 否则找一个左括号来匹配
if(str[l] == '(' && str[i] == ')') dp[l][r] = max(dp[l][r], 2 + DFS(l+1, i-1) + DFS(i+1, r));
if(str[l] == '[' && str[i] == ']') dp[l][r] = max(dp[l][r], 2 + DFS(l+1, i-1) + DFS(i+1, r));
}
if(str[r] != ')' && str[r] != ']') dp[l][r] = max(dp[l][r], DFS(l, r-1));
else {
if(str[i] == '(' && str[r] == ')') dp[l][r] = max(dp[l][r], 2 + DFS(l, i-1) + DFS(i+1, r-1));
if(str[i] == '[' && str[r] == ']') dp[l][r] = max(dp[l][r], 2 + DFS(l, i-1) + DFS(i+1, r-1));
}
}
if(dp[l][r] == -1) dp[l][r] = 0;
return dp[l][r];
}
int main() {
freopen("in", "r", stdin);
while(scanf("%s", str)) {
if(strcmp(str, "end") == 0) break;
memset(dp, -1, sizeof(dp));
int len = strlen(str);
int ans = DFS(0, len-1);
printf("%d\n", ans);
}
return 0;
}