解题思路

本题是典型的“划分型动态规划”。设字符串为 s[0..n-1]，我们用一维 DP 求解最少段数：

• 定义 dp[i]：表示将前 i 个字符（即子串 s[0..i-1]）切分成回文子串所需的最少段数。

• 初始条件：dp[0] = 0（空串不需要切分），其余 dp[i] 初始化为一个足够大的数（如 n）。

• 状态转移：枚举最后一段的起点 t（0 ≤ t ≤ i-1），若 s[t..i-1] 为回文，则

  dp[i] = min(dp[i], dp[t] + 1)
  

• 答案：dp[n]。

复杂度分析

• 时间复杂度：枚举 i 与 t 为 O(n^2)，每次回文检查 O(n)，合计 O(n^3)。
• 空间复杂度：仅使用一维数组 dp[0..n]，为 O(n)。

代码实现

Python

import sys

def is_pal(s, l, r):
    """现场判断 s[l..r] 是否为回文，双指针 O(r-l+1)"""
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True

def min_pal_parts(s):
    n = len(s)
    # dp[i]: 前 i 个字符的最少回文切分段数
    dp = [n + 1] * (n + 1)
    dp[0] = 0  # 空串 0 段

    for i in range(1, n + 1):         # 前缀长度 i
        for t in range(0, i):         # 最后一段起点 t
            if is_pal(s, t, i - 1):   # s[t..i-1] 是否回文
                dp[i] = min(dp[i], dp[t] + 1)
    return dp[n]

def main():
    data = sys.stdin.read().strip().splitlines()
    s = data[0].strip()
    print(min_pal_parts(s))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    // 现场判断回文：检查 chars[l..r]
    static boolean isPal(char[] cs, int l, int r) {
        while (l < r) {
            if (cs[l] != cs[r]) return false;
            l++; r--;
        }
        return true;
    }

    // dp[i]: 前 i 个字符的最少回文切分段数
    static int minPalParts(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;

        char[] cs = s.toCharArray();
        for (int i = 1; i <= n; i++) {          // 前缀长度 i
            for (int t = 0; t < i; t++) {       // 最后一段起点 t
                if (isPal(cs, t, i - 1)) {
                    dp[i] = Math.min(dp[i], dp[t] + 1);
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        System.out.println(minPalParts(s));
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 现场判断回文：检查 s[l..r]
bool isPal(const string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l; --r;
    }
    return true;
}

// dp[i]: 前 i 个字符的最少回文切分段数
int minPalParts(const string &s) {
    int n = (int)s.size();
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0; // 空串 0 段

    for (int i = 1; i <= n; ++i) {        // 前缀长度 i
        for (int t = 0; t < i; ++t) {     // 最后一段起点 t
            if (isPal(s, t, i - 1)) {
                dp[i] = min(dp[i], dp[t] + 1);
            }
        }
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!getline(cin, s)) return 0;
    cout << minPalParts(s) << "\n";
    return 0;
}

题面描述

给定一个只包含小写字母的字符串 $s$（长度为 $n$）。请将 $s$ 切分成若干个非空且连续的子串，使得每个子串都是回文串，并使切分得到的子串个数最少。输出这个最少个数。

输入输出

输入： 一行一个字符串 $s$。

输出： 一行输出一个整数，表示将 $s$ 分割成回文串所需的最少子串个数。

数据范围

• $1 \le n=|s| \le 400$
• 字符均为小写字母

样例

输入

aab

输出

2

说明 最优切分为 aa|b，共 2 段。

输入

abacdc

输出

2

说明 最优切分为 aba|cdc。