LeetCode 132 Palindrome Partitioning II：DP 求最小分割數

題目大意

給定字串 s，將其分割成若干回文子串，求最少分割次數。例如 "aab" → ["aa","b"]，1 次分割。

動態規劃

• isPal[i][j]：s[i..j] 是否為回文。
   isPal[i][j] = (s[i]==s[j]) && (j-i<=1 || isPal[i+1][j-1])
• cut[i]：s[0..i] 的最小分割數。
   初始 cut[i] = i（每字符獨立）。
   轉移：枚舉 j=0..i，若 isPal[j][i]，則 cut[i] = min(cut[i], (j==0? 0 : cut[j-1]+1))。

代碼實現

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if (n == 0) return 0;
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        vector<int> cut(n);
        for (int i = 0; i < n; ++i) {
            cut[i] = i; // 最壞情況：每字符獨立
            for (int j = 0; j <= i; ++j) {
                if (s[j] == s[i] && (i - j <= 1 || isPal[j+1][i-1])) {
                    isPal[j][i] = true;
                    if (j == 0) cut[i] = 0;
                    else cut[i] = min(cut[i], cut[j-1] + 1);
                }
            }
        }
        return cut[n-1];
    }
};

複雜度

• 時間：O(n²)，雙層循環檢查回文。
• 空間：O(n²) 存 isPal，可優化至 O(n)（中心擴展法實時判斷回文）。

優化思路：中心擴展 + DP

不預計算 isPal，對每個中心向兩側擴展，實時更新 cut：

for (int i = 0; i < n; ++i) {
    // 奇數長度中心 i
    for (int l = i, r = i; l >= 0 && r < n && s[l]==s[r]; --l, ++r)
        cut[r] = min(cut[r], l==0 ? 0 : cut[l-1]+1);
    // 偶數長度中心 i, i+1
    for (int l = i, r = i+1; l >= 0 && r < n && s[l]==s[r]; --l, ++r)
        cut[r] = min(cut[r], l==0 ? 0 : cut[l-1]+1);
}

時間仍 O(n²)，空間降為 O(n)。

範例

s = "cabababcbc" → 最小分割數 = 3