分割回文串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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java