本文共 2161 字，大约阅读时间需要 7 分钟。
为了解决这个问题，我们需要找到给定字符串中最长的常规括号子序列的长度。常规括号序列的定义非常明确，包括空序列、单个括号及其闭合括号，以及由常规序列组成的更长序列。
我们可以使用动态规划来解决这个问题。动态规划的状态定义为 dp[i][j]，表示从索引 i 到 j 的子串中能形成的最长常规括号序列的长度。
i > j 时，dp[i][j] 为 0；当 i == j 时，dp[i][j] 也是 0，因为单个字符无法形成括号。s[i] 和 s[j] 是一对匹配的括号（即 s[i] 是 '(' 而 s[j] 是 ')'，或者 s[i] 是 '[' 而 s[j] 是 ']'），那么 dp[i][j] = dp[i+1][j-1] + 2。k，即从 i 到 k 和从 k+1 到 j 的最长子序列之和，并取最大值。#include#include #include #include using namespace std;int main() { char str[1005]; int n; while (scanf("%s", str+1) != EOF && strcmp(str+1, "end") != 0) { n = strlen(str+1); int dp[n+2][n+2]; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) { dp[i][j] = 0; } } for (int len = 2; len <= n; ++len) { for (int i = 1; i <= n - len + 1; ++i) { int j = i + len - 1; bool is_open = (str[i] == '(' || str[i] == '['); bool is_close = (str[j] == ')' || str[j] == ']'); if (is_open && is_close) { int option1 = dp[i+1][j-1]; option1 += 2; if (option1 > dp[i][j]) { dp[i][j] = option1; } for (int k = i; k < j; ++k) { int option2 = dp[i][k] + dp[k+1][j]; if (option2 > dp[i][j]) { dp[i][j] = option2; } } } else { for (int k = i; k < j; ++k) { int option2 = dp[i][k] + dp[k+1][j]; if (option2 > dp[i][j]) { dp[i][j] = option2; } } } } } cout << dp[1][n] << endl; } return 0;}
dp 表，大小为 (n+2) x (n+2)，初始值为 0。len。i，计算结束位置 j。s[i] 和 s[j] 是否为匹配的括号对，如果是，计算包含这对括号的子序列长度。k，找出从 i 到 k 和从 k+1 到 j 的最长子序列之和。dp[1][n]，即整个字符串的最长常规括号子序列长度。转载地址：http://vifmz.baihongyu.com/