LeetCode 1278. 分割回文串 III（区间DP）
LeetCode 1278. 分割回文串 III（区间DP）
文章目录
1. 题目
给你一个由小写字母组成的字符串 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 中只含有小写英文字母。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-partitioning-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 预处理出来任意区间需要变成回文的花费cost
dp[i][k]表示前 i 个字符，拆成 k 个回文串需要的最少花费- 状态转移：枚举 j < i 时，k-1 个串的最小花费 +
cost[j, i-1]
class Solution {
public:
int palindromePartition(string s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n, 0));
int l, r, c;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
c = 0, l = i, r = j;
while(l < r)
{
if(s[l++] != s[r--])
c++;
}
cost[i][j] = c;
}
}
vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX));
dp[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int K = 1; K <= min(i, k); K++)
{
if(K==1)//分成1一个串
dp[i][K] = cost[0][i-1];
else// 分成 k 个串
{
for(int j = K-1; j < i; j++)
{
dp[i][K] = min(dp[i][K], dp[j][K-1]+cost[j][i-1]);
} // 前 j 个字符分成 K-1 个串 + [j, i-1] 区间的花费
}
}
}
return dp[n][k];
}
};时间复杂度 O ( n 3 + n 2 k ) − > O ( n 3 ) O(n^3+n^2k)->O(n^3) O(n3+n2k)−>O(n3) 28 ms 7 MB C++
- 预处理 cost 部分的复杂度还可以降低，使用区间DP
class Solution {
public:
int palindromePartition(string s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n, 0));
for(int i = 0; i < n-1; i++)
if(s[i] != s[i+1])
cost[i][i+1] = 1;
for(int len = 2; len <= n; len++)
{
for(int i = 0, j; i+len < n; i++)
{
j = i+len;
cost[i][j] = (s[i] == s[j] ? cost[i+1][j-1] : 1+cost[i+1][j-1]);
}
}
vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX));
// dp[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int K = 1; K <= min(i, k); K++)
{
if(K==1)//分成1一个串
dp[i][K] = cost[0][i-1];
else// 分成 k 个串
{
for(int j = K-1; j < i; j++)
{
dp[i][K] = min(dp[i][K], dp[j][K-1]+cost[j][i-1]);
} // 前 j 个字符分成 K-1 个串 + [j, i-1] 区间的花费
}
}
}
return dp[n][k];
}
};时间复杂度 O ( n 2 + n 2 k ) − > O ( n 2 k ) O(n^2+n^2k)->O(n^2k) O(n2+n2k)−>O(n2k) 16 ms 7 MB C++
腾讯云开发者
