UVA 11584 Partitioning by Palindromes - DP 最少回文分割

問題描述

給定小寫字母字符串（長度 ≤ 1000），將其分割成最少數量的回文子串。例：racecar → 1；fastcar → 7；aaadbccb → 3 (aaa|d|bccb)。

動態規劃

dp[i]：前 i 個字符（s[1..i]）最少分割數。
轉移：dp[i] = min{ dp[j-1] + 1 }，對所有 j ≤ i 使 s[j..i] 為回文。
初始 dp[0] = 0，答案 dp[n]。

回文判斷優化

預處理 isPal[j][i]（或中心擴展法 O(n²) 預處理所有回文區間），查詢 O(1)。總複雜度 O(n²)。

核心代碼框架

bool isPal[MAXN][MAXN];
int dp[MAXN];
char s[MAXN];

void precomputePal(int n) {
    for (int i = 1; i <= n; i++) {
        isPal[i][i] = true;
        if (i < n) isPal[i][i+1] = (s[i] == s[i+1]);
    }
    for (int len = 3; len <= n; len++)
        for (int i = 1; i+len-1 <= n; i++) {
            int j = i+len-1;
            isPal[i][j] = (s[i]==s[j] && isPal[i+1][j-1]);
        }
}

int solve(int n) {
    precomputePal(n);
    for (int i = 1; i <= n; i++) {
        dp[i] = i; // 最壞情況每字符一段
        for (int j = 1; j <= i; j++)
            if (isPal[j][i]) dp[i] = min(dp[i], dp[j-1] + 1);
    }
    return dp[n];
}

複雜度

• 時間：O(n²) 預處理回文 + O(n²) DP = O(n²)，n ≤ 1000 可行。
• 空間：O(n²) 存 isPal，可優化為中心擴展現場判斷降至 O(n) 空間。