POJ 2955 Brackets 區間 DP 括號匹配最大長度

問題

給定括號序列（長度 ≤100），只含 ()[]。求最長合法子序列長度。合法定義：空串、包裹合法串、合法串拼接。

區間 DP 狀態與轉移

dp[i][j]：區間 [i,j] 內需刪除的最少字符數使其合法。答案 = n - dp[0][n-1]。

轉移方程

• 基礎：dp[i][i] = 1（單字符必須刪除）
• 長度 l=1..n-1：
  • 若 s[i] 與 s[j] 匹配（() 或 []）：dp[i][j] = dp[i+1][j-1]
  • 枚舉分割點 k：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
char s[205];
int dp[205][205];

bool match(char a, char b) {
    return (a=='(' && b==')') || (a=='[' && b==']');
}

int main() {
    while (scanf("%s", s) == 1 && strcmp(s, "end")) {
        int n = strlen(s);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int len = 1; len < n; ++len) {
            for (int i = 0; i + len < n; ++i) {
                int j = i + len;
                dp[i][j] = INF;
                if (match(s[i], s[j])) dp[i][j] = dp[i+1][j-1];
                for (int k = i; k < j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
        printf("%d\n", n - dp[0][n-1]);
    }
    return 0;
}

複雜度與變體

• 時間 O(n³) = 10⁶，n≤100 極快
• 空間 O(n²)
• POJ 1141 為輸出具體匹配方案，本題僅求長度
• 「最少刪除」視角轉化比「最長匹配」更直觀