分割回文串在leetcode上总共有 4 道题，今天这个是第 3 题，除了第一道是中等，其他 3 道都是困难，关于前面两道我们可以看下《分割回文串》和《分割回文串 II》。这题让计算的是把字符串分割成 k 个子串，并且每个子串都是回文的，问需要修改最少字符数。我们可以先预处理子串 s[i,j] 变成回文串需要修改的字符数：1，如果 s[i]==s[j]，子串 s[i,j] 变成回文串需要修改的字符数就是 s[i+1,j-1] 变成回文串所需要修改的字符数。2，如果 s[i]!=s[j]，子串 s[i,j] 变成回文串需要修改的字符数就是 s[i+1,j-1] 变成回文串所需要修改的字符数 + 1 。预处理完之后再来进行分割，这里使用的是动态规划的思想，定义 dp[i][j] 表示把前 i 个字符分割成 j 个子串所需要修改的字符数可以得到：dp[i][j]=dp[m][j-1]+change(s,m,i-1)，这里我们需要枚举 m 的值，但要注意 m 必须大于等于 j-1 。
这题要求返回的是最少字符修改数，所以我们只需要记录最小的即可。public int palindromePartition(String s, int k) {
int length = s.length();
// palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数
int[][] palindrome = new int[length][length];
// 一列一列的从左往右（只遍历右上部分）
for (int j = 1; j for (int i = 0; i palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
// dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。
int[][] dp = new int[length + 1][k + 1];
for (int i = 1; i Arrays.fill(dp[i], Integer.MAX_VALUE);
}
// 前i个字符，分割成j个回文子串
for (int i = 1; i <= length; i++) {
// i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。
int len = Math.min(i, k);
for (int j = 1; j <= len; j++) {
if (j == 1) {
// 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1
dp[i][j] = palindrome[j - 1][i - 1];
} else {
// 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符）
for (int m = j - 1; m dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]);
}
}
}
return dp[length][k];
}
public:
int palindromePartition(string s, int k) {
int length = s.length();
// palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数
vector<vector<int>> palindrome(length, vector<int>(length, 0));
// 一列一列的从左往右（只遍历右上部分）
for (int j = 1; j for (int i = 0; i palindrome[i][j] = palindrome[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
// dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。
vector<vector<int>> dp(length + 1, vector<int>(k + 1, INT_MAX));
fill(dp[0].begin(), dp[0].end(), 0);
// 前i个字符，分割成j个回文子串
for (int i = 1; i <= length; i++) {
// i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。
int len = min(i, k);
for (int j = 1; j <= len; j++) {
if (j == 1) {
// 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1
dp[i][j] = palindrome[j - 1][i - 1];
} else {
// 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符）
for (int m = j - 1; m dp[i][j] = min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]);
}
}
}
return dp[length][k];
}
def palindromePartition(self, s: str, k: int) -> int:
length = len(s)
# palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数
palindrome = [[0] * length for _ in range(length)]
# 一列一列的从左往右（只遍历右上部分）
for j in range(1, length):
for i in range(j):
palindrome[i][j] = palindrome[i + 1][j - 1] + (0 if s[i] == s[j] else 1)
# dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。
dp = [[float('inf')] * (k + 1) for _ in range(length + 1)]
dp[0] = [0] * (k + 1)
# 前i个字符，分割成j个回文子串
for i in range(1, length + 1):
# i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。
minlen = min(i, k)
for j in range(1, minlen + 1):
if j == 1:
# 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1
dp[i][j] = palindrome[j - 1][i - 1]
else:
# 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符）
for m in range(j - 1, i):
dp[i][j] = min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1])
return dp[length][k]
