POJ 1141 括號匹配：區間 DP 求最少添加括號數

問題描述

給定由 ()[] 組成的字符串，在其中插入最少字符使其成為合法括號序列，並輸出任一合法結果。長度 ≤ 100。

DP 定義

• dp[i][j]：區間 [i,j] 變合法所需最少添加數
• cut[i][j]：最優分割點，-1 表示首尾匹配無需分割

狀態轉移

if i==j: dp[i][j]=1
else if s[i]=='(' && s[j]==')' || s[i]=='[' && s[j]==']':
    dp[i][j] = dp[i+1][j-1], cut[i][j]=-1
else:
    dp[i][j] = min over k (dp[i][k] + dp[k+1][j]), 記錄最優 k

遞歸輸出構造

void print(int i, int j) {
    if (i > j) return;
    if (i == j) {
        cout << (s[i]=='('||s[i]==')' ? "()" : "[]");
        return;
    }
    if (cut[i][j] >= 0) {
        print(i, cut[i][j]);
        print(cut[i][j]+1, j);
    } else {
        cout << s[i];
        print(i+1, j-1);
        cout << s[j];
    }
}

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int dp[MAXN][MAXN], cut[MAXN][MAXN];
string s;

int main() {
    cin >> s;
    int n = s.size();
    // 初始化 dp, cut
    // 區間 DP 填表（長度 1 到 n）
    // 遞歸輸出 print(0, n-1)
    return 0;
}

關鍵技巧

1. 區間 DP 按長度遞增填表，保證子問題已解決
2. cut 數組記錄決策，輸出時遞歸重構
3. 單字符情況特別處理：補全配對括號
4. 合法序列定義：空串、(A)、[A]、AB（A,B 合法）

此題是區間 DP 經典入門題，「括號匹配 + 最少插入 + 方案輸出」完整考察了 DP 定義、轉移、決策記錄與路徑重構全流程。