目标
给你一个由小写字母组成的字符串 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 <= 100
- s 中只含有小写英文字母。
思路
将字符串 s 分割成 k 个非空回文子串，允许修改字符中的任意字符，求修改字符的最小次数。
需要将字符串分割成 k 份并且每一份都是回文。我们需要暴力枚举所有可能的分法，并求得每种分法的修改次数，取其最小值。
核心逻辑：
- 计算所有子串变为回文的修改次数，
ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;。由于需要从i + 1转移过来，所以外层倒序。初始化数组所有值为 0，外层从倒数第二个开始，内层从 i + 1 开始。 - 从起点
i = 0开始，枚举所有终点j，无论s[i~j]是否是回文，我们直接加上ops[i][j]，k--接着以j + 1为起点继续递归搜索。 - 结束条件：
i未到结尾k先减为0，不符合要求，返回INF，可以取0x3f3f3f3fi == s.length()，如果k == 0返回0，否则说明分割的子串没有k个，不符合题意返回INF
代码
/**
* @date 2025-03-03 8:52
*/
public class PalindromePartition1278 {
public int palindromePartition(String s, int k) {
int n = s.length();
int[][] ops = new int[n][n];
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;
}
}
int[][] mem = new int[n][k + 1];
for (int[] row : mem) {
Arrays.fill(row, -1);
}
return dfs(0, k, s, ops, mem);
}
public int dfs(int i, int k, String s, int[][] ops, int[][] mem) {
int n = s.length();
if (i == n) {
return k > 0 ? 0x3f3f3f3f : 0;
}
if (k == 0) {
return 0x3f3f3f3f;
}
if (mem[i][k] != -1) {
return mem[i][k];
}
int res = Integer.MAX_VALUE;
for (int j = i; j < n; j++) {
res = Math.min(res, ops[i][j] + dfs(j + 1, k - 1, s, ops, mem));
}
mem[i][k] = res;
return res;
}
}
性能
