POJ 2955 Brackets：區間 DP 求最長合法括號子序列

問題描述

給定括號字符串（含 () 和 []），求最長合法括號子序列長度（不一定連續）。

區間 DP

dp[i][j] = 區間 [i,j] 內最長合法子序列長度。

轉移：

• 若 s[i] 與 s[k] 匹配 (() 或 [])，dp[i][j] = max(dp[i][j], dp[i+1][k-1] + 2 + dp[k+1][j])
• 或不匹配 s[i]：dp[i][j] = max(dp[i][j], dp[i+1][j])
• 枚舉 k = i+1 .. j

實際常用簡化：dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) 對所有 k，若 s[i] 匹配 s[j] 則 dp[i][j] = max(dp[i][j], dp[i+1][j-1] + 2)。

代碼

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

char s[105];
int dp[105][105];

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

int main() {
    while (scanf("%s", s), strcmp(s, "end")) {
        int n = strlen(s);
        memset(dp, 0, sizeof(dp));
        for (int len=2; len<=n; ++len)
            for (int i=0; i+len<=n; ++i) {
                int j = i+len-1;
                if (match(s[i], s[j]))
                    dp[i][j] = dp[i+1][j-1] + 2;
                for (int k=i; k