【动态规划五】回文串问题

目录

leetcode题目

一、回文子串

二、最长回文子串

三、分割回文串 IV

四、分割回文串 II

五、最长回文子序列

六、让字符串成为回文串的最少插入次数

---

leetcode题目

一、回文子串

647. 回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/palindromic-substrings/1.题目解析

返回给定字符串中所有回文子串的个数

2.算法分析

1.状态表示

如果是暴力解法，只需要先固定下标i, 然后j从i的位置开始往后一路枚举即可，下一次i++, j无需回到0号下标，因为[i, j]与[j, i]本质是同一个子串，j直接从i位置开始枚举即可, 因此我们就把状态表示定义成二维的~

dp[i][j]: s字符串中位于区间 [i, j] 的字符串, 是否是回文串 (隐含条件: i <= j)

2.状态转移方程

3.初始化

初始化的目的是 保证填表时不越界 + 后续填表是正确的

4.填表顺序

填dp[i][j]时，需要dp[i+1][j-1]的值，因此需要从下往上填每一行即可

5.返回值

返回dp表中值为true的个数即可

3.算法代码

class Solution {
public:int countSubstrings(string s) {//1.创建dp表int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));//2.填表+返回值int sum = 0;for(int i = n-1; i >= 0; i--) //从下往上填表{for(int j = i; j < n; j++){if(s[i] == s[j])dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;if(dp[i][j]) sum++; }}return sum;}
};

二、最长回文子串

5. 最长回文子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindromic-substring/1.题目解析

返回给定字符串中的最长回文子串

2.算法分析

求最长回文子串之前，先要知道哪些字符串是回文串，而题目一通过dp表，记录了[i, j]子串是否是回文串，根据dp表的值即可得到想要的结果

3.算法代码

class Solution {
public:string longestPalindrome(string s) {//1.创建dp表int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));//2.填表+返回值int begin = 0, len = 0;for(int i = n-1; i >= 0; i--) //从下往上填表{for(int j = i; j < n; j++){if(s[i] == s[j])dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;//更新结果if(dp[i][j] && len < j - i + 1) {len = j - i + 1;begin = i;}}}return s.substr(begin, len);}
};

三、分割回文串 IV

1745. 分割回文串 IV - 力扣（LeetCode）https://leetcode.cn/problems/palindrome-partitioning-iv/1.题目解析

判断给定的字符串是否能够分割成三个回文字符串， 返回true/false

2.算法分析

本题的关键就是看给定字符串能否被分割成三个回文子串， 也就是判断[0, i-1], [i, j], [j+1, n-1]这三个区间的字符串是否是回文子串，而题目一中我们用动态规划做到了使用dp表保存所有的子串是否是回文信息，因此用o(1)的时间复杂度判断即可

3.算法代码

class Solution {
public:bool checkPartitioning(string s) {//1.创建dp表int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));//2.填表for(int i = n-1; i >= 0; i--)for(int j = i; j < n; j++)if(s[i] == s[j])dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;  //3.返回值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;}
};

四、分割回文串 II

132. 分割回文串 II - 力扣（LeetCode）https://leetcode.cn/problems/palindrome-partitioning-ii/本题与 139. 单词拆分 - 力扣（LeetCode） 这道题目非常类似，大家可以对比一下两道题的做法

【动态规划三】子数组系列-CSDN博客文章浏览阅读803次，点赞20次，收藏21次。f[i]：以 i 位置为结尾的所有子数组中，最后呈现 "上升" 状态下的最长的湍流子数组的长度。g[i]：以 i 位置为结尾的所有子数组中，最后呈现 "下降" 状态下的最长的湍流子数组的长度。数组中相邻元素对之间的大小关系相反，这就是湍流数组，题目要求返回数组中最长的湍流子数组的长度。将dp表里面所有的值都初始化成1， 因此dp[i] += dp[i-1] 即可。dp[i]: [0, i]区间内的字符串, 能否被字典中的单词拼接而成。dp[i] 表示 以 i 位置元素为结尾的所有子数组的最大和。https://blog.csdn.net/m0_74126249/article/details/138501298?spm=1001.2014.3001.55011.题目解析

给定字符串s，将s分割，使得每个部分都是回文子串，求最少的分割次数

2.算法分析

1.状态表示

dp[i] 表示 [0, i] 区间上的字符串, 分割成回文串的最少分割次数

2.状态转移方程

而本题目要频繁的用到判断一个字符串是否是回文，因此用到题目一的做法，把所有子串是否是回文的信息，保存在dp表中

3.初始化

j > 0, 所以填表一定不会越界； 但是 dp[i] = min(dp[j-1] + 1, dp[i]), 所以我们把dp[i]都初始化成无穷大，不会干扰结果

4.填表顺序

从左往右

5.返回值

dp[n-1]

3.算法代码

class Solution {
public:int minCut(string s) {//1.预处理isPal表int n = s.size();vector<vector<bool>> isPal(n, vector<bool>(n, false));for(int i = n-1; i >= 0; i--)for(int j = i; j < n; j++)if(s[i] == s[j])isPal[i][j] = i + 1 < j ? isPal[i+1][j-1] : true;  //2.创建dp表 + 初始化vector<int> dp(n, INT_MAX);//3.填表for(int i = 0; i < n; i++){if(isPal[0][i])dp[i] = 0;else{for(int j = 0; j <= i; j++)if(isPal[j][i]) dp[i] = min(dp[i], dp[j-1]+1);}}//4.返回值return dp[n-1];}
};

五、最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-palindromic-subsequence/1.题目解析

与题目二的区别是子序列不一定连续，本题求的是原字符串中最长的回文子序列

2.算法分析

1.状态表示

dp[i][j]：[i, j]内的所有子序列中，最长的回文子序列的长度(隐含条件: i <= j)

2.状态转移方程

2.1  i == j时, s[i] 必然 == s[j], 因此我们可以在刚进入第一层for循环时就将dp[i][i]填成1

2.2 上面的s[i] == s[j]中的 i + 1 == j 的情况合并到 i + 1 < j 的情况中，因为当i+1 == j 时,  dp[i+1][j]都是下三角元素，默认是0, 0 + 2还是2， 不影响结果的正确性

3.初始化

无需初始化

4.填表

从下往上填表，每一行从左往右填

5.返回值

dp[0, n-1]

3.算法代码

class Solution {
public:int longestPalindromeSubseq(string s) {//1.创建dp表int n = s.size();vector<vector<int>> dp(n, vector<int>(n));//2.填表for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; //对应s[i] == s[j] && i == j 的情况for(int j = i + 1; j < n; j++){if(s[i] == s[j])dp[i][j] = dp[i+1][j-1] + 2;elsedp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}//3.返回值return dp[0][n-1];}
};

六、让字符串成为回文串的最少插入次数

1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/1.题目解析

给定字符串，可以在任意位置插入任意字符使其变为回文串，求最少的插入次数

2.算法分析

1.状态表示

dp[i][j]：s里面，[i, j]区间上的字符串, 使它成为回文串的最少插入次数

2.状态转移方程

s[i] == s[j]时，i + 1 == j 的情况可以合并到 i + 1 < j的情况中，因为i + 1 > j 时用到的dp[i+1][j-1]本质是下三角元素，直接等于0，不影响结果的正确性

3.初始化

无需初始化

4.填表顺序

从下往上填表，每一行从左往右

5.返回值

dp[0][n-1]

3.算法代码

class Solution
{
public:int minInsertions(string s) {//1.创建dp表int n = s.size();vector<vector<int>> dp(n, vector<int>(n));//2.填表for(int i = n - 1; i >= 0; i--)for(int j = i + 1; j < n; j++)if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];else dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1; //3.返回值return dp[0][n-1];}
};