【LetMeFly】1278.分割回文串 III：动态规划
力扣题目链接：https://leetcode.cn/problems/palindrome-partitioning-iii/
给你一个由小写字母组成的字符串 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 <= 100s 中只含有小写英文字母。
解题方法：动态规划
很容易想到，使用$dp[i][j]$表示$s.substr(0, i)$被切割$j$次变成非空回文串列表所需修改的最小次数。（其中$s.substr(0, i)$表示字符串$s$下标[0, i]的子串。）
因此有转移方程$dp[i][j] = \min(dp[i0][j - 1] + minop[i0 + 1][i])$，其中$0 \leq i0 \lt i$。（在$s.substr(0, i0)$被切割$j-1$次的基础上，$s.substr(i0 + 1, i)$只通过字符变换成回文。）
也就是说$minop[i][j]$代表$s.substr(i, j)$通过修改字符变成回文串所需的最小修改次数。这个数组如何得到？
又有转移方程$minop[i][j] = minop[i + 1][j - 1] + (s[i] \neq s[j])$。（如果$s[i]\neq s[j]$则需要变换其中一个字符。）
- 时间复杂度$O(n^2k)$，预处理$O(nk)$，计算结果$O(n^2k)$
- 空间复杂度$O(nk)$
AC代码
C++
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
|
class Solution {
public:
int palindromePartition(string s, int k) {
int n = s.size();
vector<vector<int>> minop(n, vector<int>(n));
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
minop[i][j] = (s[i] != s[j]) + minop[i + 1][j - 1];
}
}
vector<vector<int>> dp(n, vector<int>(k, 1000));
for (int i = 0; i < n; i++) {
dp[i][0] = minop[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < min(k, i + 1); j++) {
for (int i0 = 0; i0 < i; i0++) {
dp[i][j] = min(dp[i][j], dp[i0][j - 1] + minop[i0 + 1][i]);
}
}
}
return dp.back().back();
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| '''
Author: LetMeFly
Date: 2025-03-03 13:30:41
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-03 13:36:20
'''
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
minop = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
minop[i][j] = (s[i] != s[j]) + minop[i + 1][j - 1]
dp = [[1000] * k for _ in range(n)]
dp[0][0] = 0
for i in range(n):
dp[i][0] = minop[0][i]
for i in range(1, n):
for j in range(1, min(k, i + 1)):
for i0 in range(i):
dp[i][j] = min(dp[i][j], dp[i0][j - 1] + minop[i0 + 1][i])
return dp[-1][-1]
|
Java
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
|
class Solution {
public int palindromePartition(String s, int k) {
int n = s.length();
int[][] minop = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
minop[i][j] = minop[i + 1][j - 1];
if (s.charAt(i) != s.charAt(j)) {
minop[i][j]++;
}
}
}
int[][] dp = new int[n][k];
for (int i = 0; i < n; i++) {
dp[i][0] = minop[0][i];
for (int j = 1; j < k; j++) {
dp[i][j] = 1000;
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < Math.min(k, i + 1); j++) {
for (int i0 = 0; i0 < i; i0++) {
dp[i][j] = Math.min(dp[i][j], dp[i0][j - 1] + minop[i0 + 1][i]);
}
}
}
return dp[n - 1][k - 1];
}
}
|
Go
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
36
37
38
39
40
41
|
package main
func palindromePartition(s string, k int) int {
n := len(s)
minop := make([][]int, n)
for i, _ := range minop {
minop[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
minop[i][j] = minop[i + 1][j - 1]
if s[i] != s[j] {
minop[i][j]++
}
}
}
dp := make([][]int, n)
for i, _ := range dp {
dp[i] = make([]int, k)
for j, _ := range dp[i] {
dp[i][j] = 1000
}
}
for i, _ := range dp {
dp[i][0] = minop[0][i]
}
for i := 1; i < n; i++ {
for j := 1; j < min(k, i + 1); j++ {
for i0 := 0; i0 < i; i0++ {
dp[i][j] = min(dp[i][j], dp[i0][j - 1] + minop[i0 + 1][i])
}
}
}
return dp[n - 1][k - 1]
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源