例題 9：括號序列修正 - 動態規劃求最少添加括號數

題目描述

給定一個由括號組成的字串，要求添加最少數量的括號，使其成為一個正規括號序列。正規序列定義為：空字串、單一對匹配括號包裹的正規序列、或兩個正規序列的連接。

解題思路

採用區間動態規劃。定義 d[i][j] 表示子串 S[i...j]（閉區間）至少需要添加多少個括號才能成為正規序列。狀態轉移有兩種情況：

1. 首尾匹配：若 S[i] 與 S[j] 為一對匹配括號（即 () 或 []），則可轉移至 d[i+1][j-1]。
2. 區間分割：將區間分為 [i, k] 與 [k+1, j] 兩部分，轉移至 d[i][k] + d[k+1][j]，其中 i ≤ k < j。

邊界條件：空串 d[i+1][i] = 0，單字符 d[i][i] = 1。注意：無論是否滿足首尾匹配，都必須嘗試區間分割，否則像 [][] 這類情況會錯誤地轉移到 ][ 導致結果非最優。

輸出方案時需重新檢查最優決策，雖然增加打印複雜度，但僅在少數情況下觸發，影響可忽略。

參考代碼 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

#define maxn 210
int T, n;
string S;
int d[maxn][maxn];

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

void dp() {
    for (int i = 0; i < n; i++) {
        d[i+1][i] = 0; // 空串
        d[i][i] = 1;   // 單字符
    }
    for (int i = n-2; i >= 0; i--)          // 起點逆序
        for (int j = i+1; j < n; j++) {     // 終點順序，保證子區間已計算
            d[i][j] = n;
            if (match(S[i], S[j]))
                d[i][j] = min(d[i][j], d[i+1][j-1]);
            for (int k = i; k < j; k++)
                d[i][j] = min(d[i][j], d[i][k] + d[k+1][j]);
        }
}

void print(int i, int j) {
    if (i > j) return;
    if (i == j) { // 單字符補全
        if (S[i] == '(' || S[i] == ')') printf("()");
        else printf("[]");
        return;
    }
    int ans = d[i][j];
    if (match(S[i], S[j]) && ans == d[i+1][j-1]) {
        printf("%c", S[i]);
        print(i+1, j-1);
        printf("%c", S[j]);
        return;
    }
    for (int k = i; k < j; k++)
        if (ans == d[i][k] + d[k+1][j]) {
            print(i, k);
            print(k+1, j);
            return;
        }
}

int main() {
    cin >> T; getchar();
    while (T--) {
        getchar();
        getline(cin, S);
        n = S.length();
        dp();
        print(0, n-1);
        puts("");
        if (T) cout << endl;
    }
    return 0;
}