louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30019

題目大意:  給你一個字串，問最大可能括號匹配數為多少。 

思路:  記憶化搜索會超時，N = 500 蠻大的基本上只能Bottom-up，非常壓時間，好題。區間dp, 依照題目要求，dp[i][j]，表示i~j 這個長度 的最大括弧配對數。 開始枚舉所有字串長度。

那每個字串長度有2種情況，1種為 {A}， 如果有這種str[i] == str[j] 的話 則 dp[i][j] = dp[i+1][j-1] +1。表示去掉這個括號的最大匹配數+1。

再來還有1種是 配對AB的可能， 所以枚舉 k 中斷點， k = i+1~j-1， dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j])。 最後就由小到大建上去了，陣列為左下往右上填。 

順便附帶我原本超時的遞迴寫法。好題。

代碼:  

#include <bits/stdc++.h>
#define N 505
using namespace std;
bool match(char& c1, char &c2){
    if(c1 == '(' && c2 == ')') return 1;
    if(c1 == '[' && c2 == ']') return 1;
    if(c1 == '{' && c2 == '}') return 1;
    return 0;
}

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

/* 遞迴版本, 過4個測資 最後一個TLE
int dfs(int l, int r){
    if(l >= r) return 0;
    if(r == l + 1) return match(s[l], s[r]);
    if(memo[l][r] != -1) return memo[l][r];
    if(match(s[l], s[r]))
        memo[l][r] = 1 + dfs(l+1, r-1);
    for(int k = l; k < r; ++k)
        memo[l][r] = max(memo[l][r], dfs(l, k+1)+dfs(k+1, r));
    return memo[l][r];
}*/