ZeroJudge 解題筆記：t168.回文切割

作者：王一哲
日期：2026年11月5日


ZeroJudge 題目連結：t168.回文切割

解題想法

每組測資只有一列字串 $s$，$s$ 之中只有小寫英文字母及空格，不會有連續空格，且行首、行尾不會是空格。$s$ 的長度 $1 \leq n \leq 5000$。至少要切幾刀才能將 $s$ 的每個子字串都變成回文字串？

這題考動態規畫。開一個長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表前 $i$ 個字元最少要切幾刀，預設值為全部切成長度 $1$ 子字串的刀數，即 $dp[i] = i-1$。用一個 for 迴圈測試可能的回文中心 $mid = 0$ 到 $mid = n-1$，再分為奇數長度、偶數長度兩種狀況，從 $mid$ 向兩側擴張，取最長的回文字串，如果前 $left$ 個字元切割次數 $+ 1$ 小於前 $right + 1$ 個字元切割次數，更新 $dp[right + 1]$。最後答案在 $dp[n]$。

Python 程式碼

使用時間約為 16 ms，記憶體約為 9.8 MB，通過測試。

while True:
    try:
        s = input()
    except EOFError:
        break
   
    n = len(s)  # 長度
    dp = [i - 1 for i in range(n + 1)]  # 前 i 個字元最多切 i-1 次
    dp[0] = -1  # 避免出界

    # 測試可能的回文中心 mid = 0 ~ n-1
    for mid in range(n):
        # 狀況1，奇數長度
        left, right = mid, mid  # 由 mid 向兩側擴張，取最長的回文字串
        while left >= 0 and right < n and s[left] == s[right]:
            # 如果前 left 個字元切割次數 + 1 小於前 right + 1 個字元切割次數
            if dp[left] + 1 < dp[right + 1]:
                dp[right + 1] = dp[left] + 1
            left -= 1
            right += 1
        
        # 狀況2，偶數長度
        left, right = mid, mid + 1  # 由 mid 向兩側擴張，取最長的回文字串
        while left >= 0 and right < n and s[left] == s[right]:
            # 如果前 left 個字元切割次數 + 1 小於前 right + 1 個字元切割次數
            if dp[left] + 1 < dp[right + 1]:
                dp[right + 1] = dp[left] + 1
            left -= 1
            right += 1

    # 整個字串長度 n 需要的最小切割次數
    print(dp[n])

C++ 程式碼

使用時間約為 2 ms，記憶體約為 3.6 MB，通過測試。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(getline(cin, s)) {
        int n = (int)s.size();  // 長度
        vector<int> dp (n + 1);  // dp[i] 代表前 i 個字元至少要切幾刀
        iota(dp.begin(), dp.end(), -1);  // 前 i 個字元最多切 i-1 刀，全切成長度 1 的子字串
        
        // 測試可能的回文中心
        for(int mid = 0; mid < n; mid++) {
            // 狀況1，奇數長度
            int left = mid, right = mid;
            while(left >= 0 && right < n && s[left] == s[right]) {
                // dp[right + 1] 的狀態可以由 dp[left] + 1 轉移過來
                dp[right + 1] = min(dp[right + 1], dp[left] + 1);
                left--;
                right++;
            }
            
            // 狀況2，偶數長度
            left = mid, right = mid + 1;
            while(left >= 0 && right < n && s[left] == s[right]) {
                // dp[right + 1] 的狀態可以由 dp[left] + 1 轉移過來
                dp[right + 1] = min(dp[right + 1], dp[left] + 1);
                left--;
                right++;
            }
        }
        // 答案在 dp[n]
        cout << dp[n] << "\n";
    }
    return 0;
}

C 語言程式碼

使用時間約為 1 ms，記憶體約為 1.8 MB，通過測試。

#include <stdio.h>
#include <string.h>
#define min(a, b) ((a) < (b) ? (a) : (b))

int main() {
    char s[5001];  // 字串，題目預設最長為 5000
    // 用 fgets 讀取整行包含空格的字串，讀到 EOF 回傳 NULL，但是會讀取結尾的 \n
    while(fgets(s, sizeof(s), stdin) != NULL) {
        int n = strlen(s);  // 長度
        // 去除尾端的 \n 或 \r
        while(n > 0 && (s[n-1] == '\n' || s[n-1] == '\r')) {
            s[n-1] = '\0';
            n--;
        }
        // 避免空字串
        if (n == 0) continue;
        
        int dp[5001] = {0};  // dp[i] 代表前 i 個字元至少要切幾刀
        // 前 i 個字元最多切 i-1 刀，全切成長度 1 的子字串
        for(int i = 0; i <= n; i++) {
            dp[i] = i - 1;
        }
        
        // 測試可能的回文中心
        for(int mid = 0; mid < n; mid++) {
            // 狀況1，奇數長度
            int left = mid, right = mid;
            while(left >= 0 && right < n && s[left] == s[right]) {
                // dp[right + 1] 的狀態可以由 dp[left] + 1 轉移過來
                dp[right + 1] = min(dp[right + 1], dp[left] + 1);
                left--;
                right++;
            }
            
            // 狀況2，偶數長度
            left = mid; right = mid + 1;
            while(left >= 0 && right < n && s[left] == s[right]) {
                // dp[right + 1] 的狀態可以由 dp[left] + 1 轉移過來
                dp[right + 1] = min(dp[right + 1], dp[left] + 1);
                left--;
                right++;
            }
        }
        // 答案在 dp[n]
        printf("%d\n", dp[n]);
    }
    return 0;
}