【划分型 DP-约束划分个数】【hard】【阿里笔试】力扣1278. 分割回文串 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 <= 100
s 中只含有小写英文字母。

动态规划+预处理

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for (int span = 2; span <= n; ++span) {
            for (int i = 0; i <= n - span; ++i) {
                int j = i + span - 1;
                cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
            }
        }

        vector<vector<int>> f(n+1, vector<int>(k+1, INT_MAX));
        f[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= min(k, j); j++){
                if(j==1){
                    f[i][1] = cost[0][i-1];
                }
                else{
                    for(int m = j-1; m < i; m++){
                        f[i][j] = min(f[i][j], f[m][j-1] + cost[m][i-1]);
                    }
                }
            }
        }
        return f[n][k];
    }
};

首先我们先进行预处理，我们定义一个数组cost[i][j]来记录从i下标到j下标的所需修改的最少字符数。

然后我们定义一个二维数组f[i][j]，用 f[i][j] 表示对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数。

我们遍历数组，然后内层循环j，当j=1的时候，说明不分割，所以f[i][1] = cost[0][i-1]。当j>1的时候，我们可以列出状态转移方程：f[i][j] = min(f[i][j], f[m][j-1] + cost[m][i-1]);，想象我们有一个指针m，他的作用是在m处作为状态转移的位置，于是我们可以由f[m][j-1]也就是从m-1下标开始及之前分割成j-1个回文串需要的最少修改字符数，然后加上cost[m][i-1]也就是f[i][j]。

最后返回f[n][k]即可。

原文地址：https://blog.csdn.net/sjsjs11/article/details/143880616

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！