目录
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;
else
dp[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];
}
};
