问题背景

给你一个由小写字母组成的字符串 $s$，和一个整数 $k$。
请你按下面的要求分割字符串：

1. 首先，你可以将 $s$ 中的部分字符修改为其他的小写英文字母。
2. 接着，你需要把 $s$ 分割成 $k$ 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

数据约束

• $1\le k\le s.length\le 100$
• $s$中只含有小写英文字母。

解题过程

这题和 分割回文串 II 非常相似，看起来要求非常复杂，实际上也可以拆成两个都能用动态规划思想来解决的问题。

具体实现

class Solution {public int palindromePartition(String s, int k) {int n = s.length();int[][] changeMemo = new int[n][n];for (int[] row : changeMemo) {Arrays.fill(row, -1);}int[][] dfsMemo = new int[k][n];for (int[] row : dfsMemo) {Arrays.fill(row, -1);}return dfs(k - 1, n - 1, s.toCharArray(), dfsMemo, changeMemo);}private int dfs(int i, int right, char[] chS, int[][] dfsMemo, int[][] changeMemo) {if (i == 0) {return minChange(0, right, chS, changeMemo);}if (dfsMemo[i][right] != -1) {return dfsMemo[i][right];}int res = Integer.MAX_VALUE;for (int left = i; left <= right; left++) {res = Math.min(res, dfs(i - 1, left - 1, chS, dfsMemo, changeMemo) + minChange(left, right, chS, changeMemo));}return dfsMemo[i][right] = res;}private int minChange(int i, int j, char[] chS, int[][] changeMemo) {if (i >= j) {return 0;}if (changeMemo[i][j] != -1) {return changeMemo[i][j];}int res = minChange(i + 1, j - 1, chS, changeMemo);if (chS[i] != chS[j]) {res++;}return changeMemo[i][j] = res;}
}