精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
最近一网友发文称：博士毕业觉得自己年龄有点大，回老家的一个地级市当大学老师，结果发现落差有点大，每天处于后悔的痛苦中，已经抑郁了。
实际上只要没有都尝试过，干啥都会后悔，即便踏入社会干几年估计也会后悔。我觉得在大学当老师也挺好，大学老师又不像高中那样有早读和晚读，有些科目的老师甚至连作业都不用留，上完课就走，一周也没几节课，假期还贼多。
图片
图片
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第1278题：分割回文串 III。
问题描述
来源：LeetCode第1278题难度：困难给你一个由小写字母组成的字符串 s，和一个整数 k。请你按下面的要求分割字符串：
1，首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
2，接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。示例1：输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。
示例2：输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。
1 <= k <= s.length <= 100
s 中只含有小写英文字母。
问题分析
分割回文串在leetcode上总共有 4 道题，今天这个是第 3 题，除了第一道是中等，其他 3 道都是困难，关于前面两道我们可以看下《分割回文串》和《分割回文串 II》。这题让计算的是把字符串分割成 k 个子串，并且每个子串都是回文的，问需要修改最少字符数。我们可以先预处理子串 s[i,j] 变成回文串需要修改的字符数：1，如果 s[i]==s[j]，子串 s[i,j] 变成回文串需要修改的字符数就是 s[i+1,j-1] 变成回文串所需要修改的字符数。2，如果 s[i]!=s[j]，子串 s[i,j] 变成回文串需要修改的字符数就是 s[i+1,j-1] 变成回文串所需要修改的字符数 + 1 。预处理完之后再来进行分割，这里使用的是动态规划的思想，定义 dp[i][j] 表示把前 i 个字符分割成 j 个子串所需要修改的字符数可以得到：dp[i][j]=dp[m][j-1]+change(s,m,i-1)，这里我们需要枚举 m 的值，但要注意 m 必须大于等于 j-1 。图片
这题要求返回的是最少字符修改数，所以我们只需要记录最小的即可。JAVA：
public int palindromePartition(String s, int k) { int length = s.length(); // palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数 int[][] palindrome = new int[length][length]; // 一列一列的从左往右（只遍历右上部分） for (int j = 1; j < length; j++) for (int i = 0; i < j; i++) palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1); // dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。 int[][] dp = new int[length + 1][k + 1]; for (int i = 1; i < dp.length; i++) { Arrays.fill(dp[i], Integer.MAX_VALUE); } // 前i个字符，分割成j个回文子串 for (int i = 1; i <= length; i++) { // i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。 int len = Math.min(i, k); for (int j = 1; j <= len; j++) { if (j == 1) { // 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1 dp[i][j] = palindrome[j - 1][i - 1]; } else { // 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符） for (int m = j - 1; m < i; m++) dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]); } } } return dp[length][k];}C++：public: int palindromePartition(string s, int k) { int length = s.length(); // palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数 vector<vector<int>> palindrome(length, vector<int>(length, 0)); // 一列一列的从左往右（只遍历右上部分） for (int j = 1; j < length; j++) for (int i = 0; i < j; i++) palindrome[i][j] = palindrome[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1); // dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。 vector<vector<int>> dp(length + 1, vector<int>(k + 1, INT_MAX)); fill(dp[0].begin(), dp[0].end(), 0); // 前i个字符，分割成j个回文子串 for (int i = 1; i <= length; i++) { // i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。 int len = min(i, k); for (int j = 1; j <= len; j++) { if (j == 1) { // 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1 dp[i][j] = palindrome[j - 1][i - 1]; } else { // 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符） for (int m = j - 1; m < i; m++) dp[i][j] = min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]); } } } return dp[length][k]; }Python：def palindromePartition(self, s: str, k: int) -> int: length = len(s) # palindrome[i][j]表示子串[i,j]转化为回文串所需要的修改的字符数 palindrome = [[0] * length for _ in range(length)] # 一列一列的从左往右（只遍历右上部分） for j in range(1, length): for i in range(j): palindrome[i][j] = palindrome[i + 1][j - 1] + (0 if s[i] == s[j] else 1) # dp[i][j]表示s的前i个字符分割成k个回文子串的最少次，第一行都是 0 。 dp = [[float('inf')] * (k + 1) for _ in range(length + 1)] dp[0] = [0] * (k + 1) # 前i个字符，分割成j个回文子串 for i in range(1, length + 1): # i 个字符最多只能分割成 i 个子串，取 i 和 k 的最小值。 minlen = min(i, k) for j in range(1, minlen + 1): if j == 1: # 相当于没有分割，字符串的下标是从0开始的，所以这里要减 1 dp[i][j] = palindrome[j - 1][i - 1] else: # 开始尝试分割，从 j-1 个字符开始分割（保证任何子串都至少有一个字符） for m in range(j - 1, i): dp[i][j] = min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]) return dp[length][k]图片
笔者简介博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。《征服数据结构》专栏数组，稀疏表(Sparse Table)，单向链表，双向链表，块状链表，跳表，队列和循环队列，双端队列，单调队列，栈，单调栈，双端栈，散列表，堆，字典树(Trie树)，ArrayMap，SparseArray，二叉树，二叉搜索树(BST)，笛卡尔树，AVL树，树堆(Treap)，FHQ-Treap
……
《经典图论算法》专栏
图的介绍，图的表示方式，邻接矩阵转换，广度优先搜索(BFS)，深度优先搜索(DFS)，A*搜索算法，迭代深化深度优先搜索(IDDFS)，IDA*算法，双向广度优先搜索，迪杰斯特拉算法(Dijkstra)，贝尔曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)
……
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。