LeetCode Palindrome Partitioning II 解題詳解：動態規劃+回文預處理 O(n²) 最優解

問題描述

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

核心思路：動態規劃 + 回文查詢 O(1)

狀態定義

dp[i]：前 i 個字符（s[0..i-1]）的最少分割數。
答案 = dp[n] - 1（n 個字符最多 n-1 次分割，初始 dp[0]=0）

轉移方程

dp[i] = min(dp[j] + 1) for all 0 ≤ j < i where s[j..i-1] 是回文

關鍵優化：預處理回文查詢表

構建 isPal[i][j] 表示 s[i..j] 是否為回文。利用中心擴展或 DP 填表：
isPal[i][j] = (s[i]==s[j]) && (j-i<2 || isPal[i+1][j-1])
時間 O(n²)，空間 O(n²)，查詢 O(1)

完整 Java 代碼

public int minCut(String s) {
    if (s == null || s.length() == 0) return 0;
    boolean[][] dict = getDict(s);
    int[] dp = new int[s.length() + 1];
    dp[0] = 0;
    for (int i = 0; i < s.length(); i++) {
        dp[i+1] = i + 1;  // 最壞情況：每字符獨立
        for (int j = 0; j <= i; j++) {
            if (dict[j][i]) {
                dp[i+1] = Math.min(dp[i+1], dp[j] + 1);
            }
        }
    }
    return dp[s.length()] - 1;
}

private boolean[][] getDict(String s) {
    boolean[][] dict = new boolean[s.length()][s.length()];
    for (int i = s.length() - 1; i >= 0; i--) {
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dict[i+1][j-1]))
                dict[i][j] = true;
        }
    }
    return dict;
}

複雜度分析

• 時間：O(n²) —— 回文表 O(n²) + DP 兩層循環 O(n²)
• 空間：O(n²) —— 回文表，DP 數組 O(n)

與 Word Break 系列對比

關鍵洞察總結

1. 統計類 vs 枚舉類：求「是否存在/最值/計數」用 DP 多項式可解；求「所有方案」通常指數級
2. 預處理換查詢：回文判定從 O(n) 降為 O(1)，將總復雜度從 O(n³) 降為 O(n²)
3. 狀態定義技巧：dp[i] 定義為前 i 字符，比定義為以 i 結尾更便於轉移
4. 初始值設定：dp[i] = i 代表最壞情況（每字符獨立），保證 min 正確

本題是「區間 DP + 預處理優化」的經典範例，展示了如何將看似 O(n³) 的問題通過空間換時間優化到 O(n²)。