难度: Hard
给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：
s 中的部分字符修改为其他的小写英文字母。s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。请返回以这种方式分割字符串所需修改的最少字符数。
示例 1：
输入：s = "abc", k = 2 输出：1 解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = "aabbc", k = 3 输出：0 解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
示例 3：
输入：s = "leetcode", k = 8 输出：0
提示：
1 <= k <= s.length <= 100s 中只含有小写英文字母。运行时间: 48 ms
内存: 16.1 MB
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
# 把一个字符串划分成 k 个部分，要求将划分出来的子串修改成回文串所需要的最少操作次数
# 划分型DP
# 定义 f[i][j] 为将前j个元素划分成i组 需要修改的最少字符数
# cost 里面指的是索引 [L, j)
# 那么状态转移方程就是 f[i][j] = min(f[i-1][L] + cost(L, j) for L in range(i-1, j))
# 那么我们只要能用 O(1) 的时间得到 处理出每个区间段操作成回文串的次数就行了
# 预处理每个区间的回文串情况
n = len(s)
ss = [[0] * n for _ in range(n)]
for i in range(2, n + 1):
for j in range(n - i + 1):
ss[j][j+i-1] = ss[j + 1][j+i-2] + (0 if s[j] == s[j+i-1] else 1)
f = [[inf] * (n+1) for _ in range(k+1)]
# 初始状态的定义
f[0][0] = 0
for i in range(1, k + 1):
for j in range(i, n+1-(k-i)):
if i == 1:
f[i][j] = ss[0][j-1]
else:
for l in range(i-1, j):
f[i][j] = min(f[i-1][l] + ss[l][j-1], f[i][j])
return f[k][n]
该题解采用动态规划的方法来解决问题。首先预处理出任意区间[i, j]转变成回文串所需的最小修改次数，存储在二维数组ss中。接着定义状态f[i][j]表示将字符串的前j个字符分割成i个回文子串所需的最小修改次数。状态转移方程是通过枚举上一个回文子串的结尾位置l来更新，即f[i][j] = min(f[i-1][l] + ss[l][j-1])，其中l从i-1到j-1遍历。最终答案为f[k][n]，即整个字符串分割成k个回文子串的最小修改次数。
时间复杂度: O(n^3 + k*n^2)
空间复杂度: O(n^2 + k*n)
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
# 预处理数组，计算任意子串成为回文串的最小修改次数
ss = [[0] * n for _ in range(n)]
for i in range(2, n + 1):
for j in range(n - i + 1):
ss[j][j+i-1] = ss[j + 1][j+i-2] + (0 if s[j] == s[j+i-1] else 1)
# 动态规划数组，记录分割成i个回文子串的最小修改次数
f = [[float('inf')] * (n+1) for _ in range(k+1)]
f[0][0] = 0 # 初始化状态
for i in range(1, k + 1):
for j in range(i, n+1-(k-i)):
if i == 1:
f[i][j] = ss[0][j-1] # 只有一个分组时直接取整个字符串为一组的情况
else:
for l in range(i-1, j):
f[i][j] = min(f[i-1][l] + ss[l][j-1], f[i][j])
return f[k][n]
二维数组ss是用来存储任意子串[i, j]转变成回文串所需的最小修改次数。这个预处理步骤是为了支持动态规划中的状态转移。在动态规划过程中，每次计算分割出新的回文子串的代价时，可以直接使用ss数组得到任意子串成为回文串的修改次数，而不需要重新计算。这样大大减少了问题解决的时间复杂性，因为直接查表比重新计算每个子串是否为回文串要快得多。
在动态规划中，状态f[i][j]表示将字符串的前j个字符分割成i个回文子串的最小修改次数。遍历上一个回文子串的结尾位置l从i-1到j-1是因为，至少需要前i-1个字符来构成前i-1个回文子串。因此，l的最小值是i-1，确保每一个子串都至少有一个字符。l的最大值是j-1，意味着当前正在考虑的子串至少包含一个字符。这样的遍历范围确保了所有可能的子串划分都被考虑到，从而可以找到真正的最小修改次数来满足题目要求。
在动态规划数组f中，f[0][0]初始化为0是因为将长度为0的字符串分割成0个回文子串的修改次数自然是0（没有字符，也不需要分割）。对于其他的f[i][0]，这些表示试图将长度为0的字符串分割成多于0个回文子串，这在逻辑上是不可能的，因此应该初始化为无穷大（float('inf')），表示这种情况不可能发生。这样的初始化确保了动态规划在进行状态转移时，不会错误地考虑这些不合逻辑的情况。