---

1278. 分割回文串 III

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 1278. 分割回文串 III - 力扣

题目大意

描述：给定一个字符串 $s$ 和一个整数 $k$。

要求：将字符串 $s$ 分割成 $k$ 个非空子串，使得每个子串都变成回文串所需修改的最少字符数。修改操作是指将字符串中的某个字符改为任意其他字符。

说明：

• $1 \le k \le s.length \le 100$。
• $s$ 中只包含小写英文字母。

示例：

• 示例 1：

输入：s = "abc", k = 2
输出：1
解释：可以将 "abc" 分割成 "ab" 和 "c"，将 "ab" 改成 "aa"（修改 1 个字符）得到回文串。或者分割成 "a" 和 "bc"，将 "bc" 改成 "cc"。

• 示例 2：

输入：s = "aabbc", k = 3
输出：0
解释：直接分割为 ["aa","bb","c"]，每个子串已经是回文串，无需修改。

解题思路

思路 1：动态规划

1. 阶段划分

这是一个将字符串切成 $k$ 段的划分型 DP。先计算任意子串 $s[i:j]$ 变成回文串需要修改的次数，然后再用 DP 求解最小总修改次数。

阶段按"已经处理到的位置"和"已经切成的段数"划分。

2. 定义状态

第一步：定义 $cost[i][j]$ 表示将子串 $s[i:j]$（从 $i$ 到 $j$，包含两端）变成回文串所需的最少修改次数。

第二步：定义 $dp[i][j]$ 表示将 $s$ 的前 $i$ 个字符（$s[0:i]$）分割成 $j$ 个子串所需的最少总修改次数。最终答案为 $dp[n][k]$。

3. 状态转移方程

$cost$ 的转移：对于子串 $s[i:j]$，如果两端的字符 $s[i] \ne s[j]$，则需要修改其中一个（1 次），中间的字符变成回文串需要 $cost[i+1][j-1]$ 次：

$$cost[i][j] = cost[i+1][j-1] + (0 \ \text{if} \ s[i] == s[j] \ \text{else} \ 1)$$

$dp$ 的转移：将前 $i$ 个字符分成 $j$ 段，可以枚举最后一段的起始位置 $m$（即最后一段为 $s[m:i-1]$）：

$$dp[i][j] = \min_{m \ge j-1} (dp[m][j-1] + cost[m][i-1])$$

其中 $m$ 从 $j-1$ 到 $i-1$（因为前 $j-1$ 段至少需要 $j-1$ 个字符）。

4. 初始条件

• $cost[i][i] = 0$（单字符本身就是回文）。
• $cost[i][i+1] = 0$ 如果 $s[i] == s[i+1]$，否则为 $1$（两个字符）。
• $dp[0][0] = 0$。
• $dp[i][j] = \infty$（初始化为较大值）。

5. 最终结果

$dp[n][k]$。

6. 结合示例走一遍

$s = \text{"abc"}, k = 2$

先计算 $cost$：

• $cost[0][2]$：两端 $a \ne c$ → $cost[1][1] + 1 = 0 + 1 = 1$（将 $a$ 改成 $c$ 或将 $c$ 改成 $a$）
• $cost[0][1]$：$a \ne b$ → $1$
• $cost[0][0]$：$0$
• $cost[1][2]$：$b \ne c$ → $1$
• $cost[1][1]=0, cost[2][2]=0$

计算 $dp$：

• $dp[0][0] = 0$
• $i=1$：$dp[1][1] = dp[0][0] + cost[0][0] = 0 + 0 = 0$
• $i=2$：
  • $dp[2][1] = dp[0][0] + cost[0][1] = 0 + 1 = 1$（"ab" 整体变回文需 1 次）
  • $dp[2][2] = dp[1][1] + cost[1][1] = 0 + 0 = 0$（"a"+"b" 各需 0 次）
• $i=3$：
  • $dp[3][1] = dp[0][0] + cost[0][2] = 0 + 1 = 1$（"abc" 整体变回文需 1 次）
  • $dp[3][2] = \min(dp[1][1] + cost[1][2], dp[2][1] + cost[2][2]) = \min(0+1, 1+0) = 1$

结果为 $dp[3][2] = 1$。

思路 1：代码

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)

        # 计算 cost[i][j]：s[i..j] 变成回文串的最小修改次数
        cost = [[0] * n for _ in range(n)]
        for length in range(2, n + 1):          # 子串长度
            for i in range(n - length + 1):
                j = i + length - 1
                # 两端字符不同则需要修改一次
                cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)

        # dp[i][j]：前 i 个字符分成 j 段的最小修改次数
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        for i in range(1, n + 1):
            # 最多分成 min(i, k) 段
            for j in range(1, min(i, k) + 1):
                # 枚举最后一段的起始位置 m
                for m in range(j - 1, i):
                    dp[i][j] = min(dp[i][j],
                                   dp[m][j - 1] + cost[m][i - 1])

        return dp[n][k]

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是字符串长度。计算 $cost$ 需要 $O(n^2)$，计算 $dp$ 需要 $O(n^2 \times k)$，最坏 $O(n^3)$。$n \le 100$，$100^3 = 10^6$，在 Python 中可顺利通过。
• 空间复杂度：$O(n^2)$，存储 $cost$ 数组和 $dp$ 数组。