【Leetcode每日一题】1278.分割回文串III

问题背景

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

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

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

数据约束 1 ≤ k ≤ s . l e n g t h ≤ 100 1 \le k \le s.length \le 100 1≤k≤s.length≤100 s s 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; } }