分割回文串3Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个由小写字母组成的字符串 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 中只含有小写英文字母。
# 思路
cache[i][j] 表示 s 中索引 i 到 j 构成回文串的最小步数
# 解法
class Solution {
public int palindromePartition(String s, int K) {
int len = s.length();
// cache[i][j] 表示 s 中索引 i 到 j 构成回文串的最小步数
int[][] cache = new int[len][len];
// 填充
for (int i = len-1; i > 0; i--) {
for (int j = i-1; j < len-1; j++) {
// 状态转移
cache[i-1][j+1] = cache[i][j] + (s.charAt(i-1) == s.charAt(j+1) ? 0 : 1);
}
}
// dp[i][k] 表示划分为 k 个时，s 中 0~i 构成回文串的所需最小步数
int[][] dp = new int[len][K];
// 初始化
for (int i = 1; i < len; i++) {
dp[i][0] = cache[0][i];
}
for (int i = 1; i < len; i++) {
for (int k = 1; k < K; k++) {
// 初始化
dp[i][k] = Integer.MAX_VALUE;
for (int j = i; j >= k; j--) {
// 状态转移
dp[i][k] = Math.min(dp[i][k], dp[j-1][k-1] + cache[j][i]);
}
}
}
return dp[len-1][K-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 总结
- 分析出几种情况，然后分别对各个情况实现
