题目大意：
分割回文串 III
给你一个由小写字母组成的字符串 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中只含有小写英文字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1278
解题思路分析：
典型的动态规划（DP），或者说是递归加记忆数组的题目。为什么说是典型，原因在于，我们无法一眼算出如何分割字符串能够得到最优解，这种情况下，通常我们需要遍历所有分割可能，然后比较出一个最优解作为返回结果。
我们先从字符串头部开始分割出第一部分，该部分的长度范围在1到字符串长度length – k（k是剩下要分割的个数）之间。比如，字符串长度为5，我们要将其分成3部分，那么第一部分的最小长度可以为1 ([0, 0]区间)，最大长度只能为3，即[0, 2]区间（length-k=5-3=2），如果第一部分大于这个长度，那么剩下的元素就无法满足总的分割次数。我们从最小长度遍历到最大长度，分别计算出当前子字符串变为回文所需的更改次数，然后再加上剩下的部分完全分割后所需的最小次数，取最小值即为当前的返回结果。剩下部分的分割可以交给子问题去解决（递归），子问题的处理逻辑与当前相同。递归结束条件是当子字符串长度等于k时，返回0（将长度为k的字符串分成k部分，每部分长度为1，都是回文，无需更改）。另外，如果字符串长度小于k，也可以返回0。（无法分割，属于不合理解）
另外需要注意一点，如果当前的k值为1时，也就是说我们别无选择，当前字符串是不能分割的。
实现代码：
Integer[][] memo; // 记忆数组
public int palindromePartition(String s, int k) {
memo = new Integer[s.length()][k+1];
return help(s,k,0); // 递归求解
}
// s为字符串
// k为分割数
// left为当前index
int help(String s, int k, int left){
// 如果当前index到字符串末尾小于等于k，返回0（解释看上文）
if (s.length()-left<=k) return 0;
// 如果记忆数组不为空，直接返回
if(memo[left][k]!=null) return memo[left][k];
// 返回结果
int res=Integer.MAX_VALUE;
// 如果当前k为1时，无法分割，右区间直接设置到字符串末尾
// 反之，左区间指针等于右区间指针（区间长度为1）
int right =k==1?s.length()-1:left;
// 循环当前分割的可能长度范围[left, right(i)]
for(int i=right;i<=s.length()-k;i++){
// 当前分割区间是[left, i]
int l =left,r=i;
// 计算将该区间变成回文需要变换的次数
int count =0;
while(l<r){
if(s.charAt(l++)!=s.charAt(r--)) count++;
}
// 如果次数大于等于之间计算的最小值，继续
if(count>=res) continue;
// 当前区间变换次数加上后面部分需要变换的次数为当前解
// 更新最小值为当前最优解
res=Math.min(res, count+help(s,k-1,i+1));
}
memo[left][k]=res; // 将结果存入记忆数组
return res;
}本题解法执行时间为4ms。
Runtime: 4 ms, faster than 90.85% of Java online submissions for Palindrome Partitioning III.
Memory Usage: 34.1 MB, less than 100.00% of Java online submissions for Palindrome Partitioning III.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1278-palindrome-partitioning-iii-解题思路分析/