《算法题讲解指南：动态规划算法--回文串问题》--35.回文子串，36. 最长回文子串，37.分割回文串 IV，38.分割回文串 II，39.最长回文子序列，40.让字符串成为回文串的最少插入次数

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录35.回文子串题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析36. 最长回文子串题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析37.分割回文串 IV题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析38.分割回文串 II题目链接题目描述题目示例解法动态规划算法思路C算法代码算法总结及流程解析39.最长回文子序列题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析40.让字符串成为回文串的最少插入次数题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语35.回文子串题目链接647. 回文子串 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路我们可以先「预处理」一下将所有子串「是否回文」的信息统计在dp表里面然后直接在表里面统计true的个数即可。1.状态表示为了能表示出来所有的子串我们可以创建一个n*n的二维dp表只用到「上三角部分」即可。其中dp[ i ][ j ]表示s字符串[ij]的子串是否是回文串。2.状态转移方程对于回文串我们一般分析一个「区间两头」的元素i.当 s[ i ] ! s[ j ] 的时候不可能是回文串dp[i][j]0 ;ii.当 s[ i ] s[ j ] 的时候根据长度分三种情况讨论长度为1 也就是i j:此时一定是回文串dp[i][j] true;长度为2 也就是i 1 j:此时也一定是回文串dp[i][j] true ;长度大于 2此时要去看看[i 1j-1]区间的子串是否回文dp[i][j] dp[i 1][j - 1]。综上状态转移方程分情况谈论即可。3.初始化因为我们的状态转移方程分析的很细致因此无需初始化。4.填表顺序根据「状态转移方程」我们需要「从下往上」填写每一行每一行的顺序无所谓。5.返回值根据「状态表示和题目要求」我们需要返回dp表中true的个数。C算法代码class Solution { public: int countSubstrings(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n)); //bp[i][j]表示[i, j]区间的子串是否是回文(i j) for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(i j) { dp[i][j] true; } else if(j i 1) { dp[i][j] s[i] s[j] ? true : false; } else { //因为我要知道[i, j]区间是否回文需要知道[i 1, j - 1]区间是否回文 //所以i需要从后往前遍历而j需要从前往后遍历 //才能从dp[i 1][j - 1]推出dp[i][j] dp[i][j] s[i] s[j] ? dp[i 1][j - 1] : false; } //第二种写法(逻辑完全一样) // if(s[i] s[j]) // { // if(i j || (i 1) j) // { // dp[i][j] true; // } // else // { // dp[i][j] dp[i 1][j - 1]; // } // } // else // { // dp[i][j] false; // } } } int count 0; for(int i 0; i n; i) { for(int j 0; j n; j) { if(dp[i][j] true) { count; } } } return count; } };算法总结及流程解析36. 最长回文子串题目链接5. 最长回文子串 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路a.我们可以先用dp 表统计出「所有子串是否回文」的信息b.然后根据dp表示true的位置得到回文串的「起始位置」和「长度」。那么我们就可以在表中找出最长回文串。关于「预处理所有子串是否回文」已经在上面一道题目里面讲过这里就不再赘述了。C算法代码class Solution { public: string longestPalindrome(string s) { //动态规划 int n s.size(); int begin 0, len 0; vectorvectorbool dp(n, vectorbool(n)); for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(s[i] s[j]) { if(i j || i 1 j) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } else { dp[i][j] false; } if(dp[i][j] true) { if(len j - i 1) { len j - i 1; begin i; } } } } return s.substr(begin, len); } };算法总结及流程解析37.分割回文串 IV题目链接1745. 分割回文串 IV - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路题目要求一个字符串被分成「三个非空回文子串」乍一看要表示的状态很多有些无从下手。其实我们可以把它拆成「两个小问题」i.动态规划求解字符串中的一段非空子串是否是回文串;ii.枚举三个子串除字符串端点外的起止点查询这三段连续非空子串是否是回文串。那么这道困难题就免秒变为简单题啦变成了一道枚举题。关于预处理所有子串是否回文已经在前面讲过这里就不再赘述。C算法代码class Solution { public: bool checkPartitioning(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n)); for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(i j) { dp[i][j] true; } else if(j i 1) { dp[i][j] s[i] s[j] ? true : false; } else { dp[i][j] s[i] s[j] ? dp[i 1][j - 1] : false; } } } //得到了所有子串是否为回文的信息后 //就可以通过两个变量ij将字符串一分为三判断三个连续子串是否同时回文 for(int i 1; i n - 1; i) { for(int j i; j n - 1; j) { if(dp[0][i - 1] dp[i][j] dp[j 1][n - 1]) { return true; } } } return false; } };算法总结及流程解析38.分割回文串 II题目链接132. 分割回文串 II - 力扣LeetCode题目描述题目示例解法动态规划算法思路1.状态表示根据「经验」继续尝试用i位置为结尾定义状态表示看看能否解决问题dp[ i ]表示s中[0i]区间上的字符串最少分割的次数。2.状态转移方程状态转移方程一般都是根据「最后一个位置」的信息来分析设 0ji那么我们可以根据 j ~ i 位置上的子串是否是回文串分成下面两类i.当[j,i]位置上的子串能够构成一个回文串那么dp[i]就等于[0j-1]区间上最少回文串的个数1即dp[i]dp[j-1] 1;ii.当[ji]位置上的子串不能构成一个回文串此时j位置就不用考虑。由于我们要的是最小值因此应该循环遍历一遍j的取值拿到里面的最小值即可。优化我们在状态转移方程里面分析到要能够快速判读字符串里面的子串是否回文。因此我们可以先处理一个dp表里面保存所有子串是否回文的信息。3.初始化观察「状态转移方程」我们会用到j-1位置的值。我们可以思考一下当j0的时候表示的区间就是[0i]。如果[0i]区间上的字符串已经是回文串了最小的回文串就是1 了j往后的值就不用遍历了。因此我们可以在循环遍历j的值之前处理j0的情况然后j从1开始循环。但是为了防止求min操作时0干扰结果。我们先把表里面的值初始化为「无穷大」。4.填表顺序毫无疑问是「从左往右」。5.返回值:根据「状态表示」应该返回 dp[n-1]。C算法代码class Solution { public: int minCut(string s) { int n s.size(); vectorvectorbool dp_string(n, vectorbool(n)); for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(s[i] s[j]) { if(i j || i 1 j) { dp_string[i][j] true; } else { dp_string[i][j] dp_string[i 1][j - 1]; } } else { dp_string[i][j] false; } } } vectorint dp_cut(n, INT_MAX); dp_cut[0] 0; for(int j 1; j n; j) { for(int i 1; i j; i) { if(dp_string[i][j] true) { dp_cut[j] min(dp_cut[i - 1] 1, dp_cut[j]); } } //特判i为0也就是[0, j]区间整个子串是否回文 if(dp_string[0][j] true) { dp_cut[j] 0; } } return dp_cut[n - 1]; } };算法总结及流程解析39.最长回文子序列题目链接516. 最长回文子序列 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示:关于「单个字符串」问题中的「回文子序列」或者「回文子串」我们的状态表示研究的对象一般都是选取原字符串中的一段区域[ij]内部的情况。这里我们继续选取字符串中的一段区域来研究dp[ i ][ j ]表示s字符串[ij]区间内的所有的子序列中最长的回文子序列的长度。2.状态转移方程关于「回文子序列」和「回文子串」的分析方式一般都是比较固定的都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话「去掉首尾两个元素之后依旧是回文串」「首尾加上两个相同的元素之后也依旧是回文串」。因为根据「首尾元素」的不同可以分为下面两种情况i.当首尾两个元素「相同」的时候也就是s[i] s[j]:那么[ij]区间上的最长回文子序列应该是[i 1j-1]区间内的那个最长回文子序列首尾填上s[i]和s[j]此时dp[i][j]dp[i1][j-1] 2ii.当首尾两个元素不「相同」的时候也就是s[i]!s[j]:此时这两个元素就不能同时添加在一个回文串的左右那么我们就应该让s[i]单独加在一个序列的左边或者让s[j]单独放在一个序列的右边看看这两种情况下的最大值单独加入 s[i]后的区间在[ij- 1]此时最长的回文序列的长度就是dp[i][j-1];单独加入 s[j]后的区间在[i 1j]此时最长的回文序列的长度就是dp[i 1][j];取两者的最大值于是 dp[i][j] max(dp[i][j-1]dp[i 1][j])综上所述状态转移方程为当s[i] s[j]时: dp[i][j] dp[i 1][j-1] 2当 s[i] ! s[j]时: dp[i][j] max(dp[i][j -1] dp[i 1][j])3.初始化我们的初始化一般就是为了处理在状态转移的过程中遇到的一些边界情况因为我们需要根据状态转移方程来分析哪些位置需要初始化。根据状态转移方程dp[i][j]dp[i 1][j-1] 2 我们状态表示的时候选取的是一段区间因此需要要求左端点的值要小于等于右端点的值因此会有两种边界情况i.当ij的时候i1就会大于j-1 此时区间内只有一个字符。这个比较好分析dp[i][j]表示一个字符的最长回文序列一个字符能够自己组成回文串因此此时dp[i][j]1;ii.当i1j的时候i 1也会大于j-1 此时区间内有两个字符。这样也好分析当这两个字符相同的时候dp[i][j]2;不相同的时候d[i][j]对于第旦种边界情况我们在填表的时候就可以同步处理。对于第二种边界情况dp[i 1][j-1]的值为 0不会影响最终的结果因此可以不用考虑。4.填表顺序:根据「状态转移」我们发现在dp表所表示的矩阵中dp[i1]表示下一行的位置dp[j-1]表示前一列的位置。因此我们的填表顺序应该是「从下往上填写每一行」「每一行从左往右」。这个与我们一般的填写顺序不太一致。5.返回值:根据「状态表示」我们需要返回[0n-1]区域上的最长回文序列的长度因此需要返回dp[0][n - 1]。C算法代码class Solution { public: int longestPalindromeSubseq(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n)); for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(s[i] s[j]) { if(i j) { dp[i][j] 1; } else if(i 1 j) { dp[i][j] 2; } else { dp[i][j] dp[i 1][j - 1] 2; } } else { //这里如果写成dp[i 1][j - 1]是不够的 //这种情况所得到的最长回文子序列也就是[i 1, j - 1] //但可能s[i]和s[j - 1]或者s[i 1]和s[j]是相等的 //使得这两个情况所得到的回文子序列更长 //而这两种情况包含了上面情况所以只需要取这两种情况最大值即可 dp[i][j] max(dp[i 1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; } };算法总结及流程解析40.让字符串成为回文串的最少插入次数题目链接1312. 让字符串成为回文串的最少插入次数 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示关于「单个字符串」问题中的「回文子序列」或者「回文子串」我们的状态表示研究的对象一般都是选取原字符串中的一段区域[ij]内部的情况。这里我们继续选取字符串中的一段区域来研究状态表示dp[ i ][ j ]表示字符串[ij]区域成为回文子串的最少插入次数。2.状态转移方程关于「回文子序列」和「回文子串」的分析方式一般都是比较固定的都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话「去掉首尾两个元素之后依旧是回文串」「首尾加上两个相同的元素之后也依旧是回文串」。因为根据「首尾元素」的不同可以分为下面两种情况i.当首尾两个元素「相同」的时候也就是s[ i ] s[ j ]1.那么[ij]区间内成为回文子串的最少插入次数取决于[i 1j - 1]区间内成为回文子串的最少插入次数;2.若 i j 或 i j - 1 ( [i 1j-1] 不构成合法区间 )此时只有1~2个相同的字符[ij]区间一定是回文子串成为回文子串的最少插入次数是0。此时dp[ i ][ j ] i j - 1 ? 0 : dp[i 1][j - 1];ii.当首尾两个元素「不相同」的时候也就是s[ i ] ! s[ j ]1.此时可以在区间最右边补上一个 s[i]需要的最少插入次数是[i 1j]成为回文子串的最少插入次数本次插入即dp[ i ][ j ] dp[ i 1][ j ] 1;2.此时可以在区间最左边补上一个 s[j]需要的最少插入次数是[ij 1]成为回文子串的最少插入次数本次插入即 dp[ i ][ j ] dp[ i ][ j 1] 1 ;综上所述状态转移方程为:当 s[ i ] s[ j ] 时dp[ i ][ j ] i j - 1 ? 1 : dp[ i 1j - 1]当 s[ i ] ! s[ j ] 时dp[ i ][ j ] min( dp[ i 1][ j ], dp[ i ][ j - 1 ] ) 1。3.初始化根据「状态转移方程」没有不能递推表示的值。无需初始化。4.填表顺序根据「状态转移」我们发现在dp表所表示的矩阵中dp[i1]表示下一行的位置dp[j-1]表示前一列的位置。因此我们的填表顺序应该是「从下往上填写每一行」「每一行从左往右」。这个与我们一般的填写顺序不太一致。5.返回值根据「状态表示」我们需要返回[0n-1]区域上成为回文子串的最少插入次数因此需要返回 dp[0][n-1]。C算法代码class Solution { public: int minInsertions(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n)); //dp[i][j]表示区间[i, j]成为回文子串的最少插入次数 for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(s[i] s[j]) { if(i j || i 1 j) { dp[i][j] 0; } else { dp[i][j] dp[i 1][j - 1]; } } else { //s[i] ! s[j] //可能s[i] s[j - 1]所以相当于先在i前面插入s[j]转变成上面的情况 //可能s[i 1] s[j]所以相当于先在j后面插入s[i]转变成上面的情况 dp[i][j] min(1 dp[i][j - 1], 1 dp[i 1][j]); } } } return dp[0][n - 1]; } };算法总结及流程解析结束语到此35.回文子串36. 最长回文子串37.分割回文串 IV38.分割回文串 II39.最长回文子序列40.让字符串成为回文串的最少插入次数 这六道算法题就讲解完了。核心思路包括1使用二维DP表预处理子串回文信息2状态转移方程根据不同字符情况分类处理3填表顺序采用从下往上、从左往右的特殊方式。具体涵盖了回文子串计数、最长回文子串、分割回文串及回文子序列等典型问题。希望大家能有所收获