给你一个由小写字母组成的字符串 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 中只含有小写英文字母。
动态规划+预处理
class Solution {
public:int palindromePartition(string s, int k) {int n = s.size();vector<vector<int>> cost(n, vector<int>(n));for (int span = 2; span <= n; ++span) {for (int i = 0; i <= n - span; ++i) {int j = i + span - 1;cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);}}vector<vector<int>> f(n+1, vector<int>(k+1, INT_MAX));f[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= min(k, j); j++){if(j==1){f[i][1] = cost[0][i-1];}else{for(int m = j-1; m < i; m++){f[i][j] = min(f[i][j], f[m][j-1] + cost[m][i-1]);}}}}return f[n][k];}
};
首先我们先进行预处理，我们定义一个数组cost[i][j]来记录从i下标到j下标的所需修改的最少字符数。
然后我们定义一个二维数组f[i][j]，用 f[i][j] 表示对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数。
我们遍历数组，然后内层循环j，当j=1的时候，说明不分割，所以f[i][1] = cost[0][i-1]。当j>1的时候，我们可以列出状态转移方程：f[i][j] = min(f[i][j], f[m][j-1] + cost[m][i-1]);，想象我们有一个指针m，他的作用是在m处作为状态转移的位置，于是我们可以由f[m][j-1]也就是从m-1下标开始及之前分割成j-1个回文串需要的最少修改字符数，然后加上cost[m][i-1]也就是f[i][j]。
最后返回f[n][k]即可。
