【动态规划】回文串问题
回文串问题
- 1.回文子串
- 2.最长回文子串
- 3.分割回文串 IV
- 4.分割回文串 II
- 5.最长回文子序列
- 6.让字符串成为回文串的最少插入次数
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.回文子串
题目链接：647. 回文子串
题目分析：
子串和子数组是一样的。
具有不同开始位置或者结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
算法原理：
对于这道题相比于动态规划，中心扩展算法和马拉车算法更优秀。
中心扩展算法：时间复杂度O(N^2)，空间复杂度O(1)
马拉车算法：时间复杂度O(N)，空间复杂度O(N)
动态规划：时间复杂度O(N^2)， 空间复杂度O(N^2)
动态规划虽然这里不是最优解，但是它的思想可以让有些回文串的困难题变成容易题。
能够将所有的子串是否是回文的信息，保存在 dp 表里面
1.状态表示
既然要把所有子串都放在dp表里面，一个一维dp肯定不够，
dp[i][j] 表示 s 字符串 [i, j] 的子串，是否是回文串
2.状态转移方程
判断 i - > j 是否是回文串，必须首先 i 位置 和 j 位置字符是相等的，如果都不相等，即使里面在好， i - > j 子串也不回文串
i 位置 和 j 位置字符相等，这里分三种情况：
i == j ， ij同一个位置 是回文子串
i + 1 == j ，ij相邻 是回文子串
还有就是 i -> j 中间有别的字符，那就看 i + 1 位置 到 j - 1 位置的子串是否是回文子串，而i + 1 位 到 j - 1 是否是回文子串就在dp[i + 1][j - 1]
3.初始化
会发生越界的就只有 dp[i + 1][j -1]，但是它会发生越界情况都已经在 i == j，i + 1 < j 这两种情况考虑到了。
4.填表顺序
dp[i][j] 可能会用到 dp[i + 1][j -1]，所以从下往上填。
5.返回值
统计dp表中true的个数。
class Solution {
public:
int countSubstrings(string s) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
int ret = 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]) ret += 1; // 统计个数
}
}
return ret;
}
};
2.最长回文子串
题目链接： 5. 最长回文子串
题目描述：
算法原理：
如果上面那道题搞懂了，这道题完全直接就去做就行了。可以这样做：
判断子串是否是回文 —> 用 dp 表，统计所有子串是否是回文的信息 —> 根据 dp 表的起始位置得到我们想要的结果。
起始位置 i，回文串结束位置 j，回文串长度 j - 1 + 1
1.状态表示
dp[i][j] 表示 s 字符串 [i, j] 的子串，是否是回文串
2.状态转移方程
3.初始化
无需初始化，当用到 dp[i+1][j-1] 是有条件的，当 i + 1 < j才会用，此时不会越界。只有当 i == j，i + 1 == j 才会越界，但是我们已经特殊处理过了。
4.填表顺序
dp[i][j] 可能会用到 dp[i + 1][j -1]，所以从下往上填。
5.返回值
dp 里面值为 true 的情况下，长度最大的子串的起始位置以及长度
class Solution {
public:
string longestPalindrome(string s) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
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] && j - i + 1 > len)
{
begin = i;
len = j - i + 1;
}
}
}
}
return s.substr(begin,len);
}
};
3.分割回文串 IV
题目链接： 1745. 分割回文串 IV
题目分析：
给你一个字符串 s，把它分成三个部分，如果这三个部分全都是回文子串，返回true，否则false。
算法原理：
我们先想如何暴力解决这个问题，我们可以把所有的分割出来的三个子串枚举一下，然后判断是否是回文就可以了。我们可以这样枚举，固定一个 i 位置，一个 j 位置，i j 表示的是分割出来的第二个字符串的起始位置和结束位置，那整个字符串，就被分成 [0, i -1]，[i, j]， [j+1, n-1] 三个部分。
如果我们能够快速判断这三个子串是否是回文就好了。
别忘记，回文子串，我们可以用 dp 表保存所有子串是否是回文的信息。
也就是说用动态规划，搞一个二维的dp表，保存所有子串是否是回文的信息，接下来在枚举所有第二个字符串的起始位置和结束位置，仅需在dp表里面查一下三个部分是否是回文就行了。
class Solution {
public:
bool checkPartitioning(string s) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
// 1.用 dp 把所有的子串是否是回文预处理⼀下
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
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;
}
}
// 2.枚举所有的第二个字符串的起始位置以及结束位置,这样就能把字符串划分三个部分
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;
}
};
4.分割回文串 II
题目链接： 132. 分割回文串 II
题目描述：
1.状态表示
这道题和 “单词拆分” 类似，需要从左往右一个一个试，所以我们可以根据经验 + 题目要求 来找出状态表示。之前的题用某个位置为结尾的状态表示，推不出状态转移方程。。经验失效了，所以用别的方法解决。这道题可以。
dp[i] 表示： s [0,i] 区间上的最长的子串，最少分割次数
2.状态转移方程
仅需考虑[0,i]区间的子串，不需要考虑后面的。
如果[0,i]区间的子串本身就是回文了，根本不需要切割了。
如果[0,i]区间的子串不是回文，这个时候就想dp[i]能不能用之前的状态来表示一下，如果可以就能推出状态转移方程。
如果 [0,i] 区间 来一个 j 切出来一个 [j,i] 的子串，如果[j,i] 是一个回文串，接下来在 [0,j-1] 看看切多少刀，然后再加上切出来的[j,i] 这一刀就可以了。
我们要经常判断 0 ~ i，j ~ i 是否是回文，总体时间复杂度O(N^3)。
所以优化一下：
回文子串，二维 dp 表，将所有的子串是否是回文的信息，保存在 dp 表里面。
这样就可以以O(1)时间复杂度在 dp 表中判断是否是回文了，时间复杂度降到O(N^2)
3.初始化
这道题是不用初始化的，因为只有 j == 0 dp[j -1]才会越界，但是 j > 0。但是因为dp[i] 要找最小，如果不初始化 dp表里面都是0，选最小会有影响，所以 dp 表内所有的值都初始化为无穷大。
4.填表顺序
从左往右
5.返回值
dp[i] 表示： s [0,i] 区间上的最长的子串，最少分割次数，这道题要求整个区间的最少分割次数，所以返回 dp[n-1]
class Solution {
public:
int minCut(string s) {
int n = s.size();
//预处理,将所有子串是否是回文的信息,保存在 isPal 表里面
vector<vector<bool>> isPal(n,vector<bool>(n));
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;
vector<int> dp(n,INT_MAX);
for(int i = 0; i < n; ++i)
{
if(isPal[0][i]) dp[i] = 0;
else
for(int j = 1; j <= i; ++j)
if(isPal[j][i])
dp[i] = min(dp[j - 1] + 1, dp[i]);
}
return dp[n-1];
}
};
5.最长回文子序列
题目链接：516. 最长回文子序列
题目描述：
算法原理：
1.状态表示
关于子序列的题我们做了很多了，前面都是以 i 位置为结尾 + 题目要求分析问题
这里我们先根据之前的经验来一个状态表示
dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长回文子序列的长度。
以 i 位置元素为结尾，势必会用到 i 位置之前，i - 1， i - 2，i - 3。。。这种找子序列的套路可以跟在它们任意后面，根据 dp[i -1]，dp[i - 2]，dp[i - 3] 去填 dp[i]。但是这里有个问题上面状态表示只知道前面最长回文子序列的长度，并不知道回文子序列是什么，加上 i 位置是否构成回文子序列。因此上面状态表示不对。
在回文子串哪里，如果以 i 位置为起点，j 位置为结束的子串是一个回文子串，i 前面加一个字符，j 后面加一个字符，如果相等，依旧是一个回文子串。
比如在s 字符串里面依旧选一个 i -> j 区间，如果知道这个区间内的最长回文子序列的长度，如果 i 前面字符 和 j 后面字符是一样的。那也能推出来 i - 1 -> j +1 区间回文子序列的长度。在原有基础上多加一个2。因此状态表示
dp[i][j] 表示：s 字符串 [i, j] 区间内的所有子序列，最长的回文子序列的长度。
2.状态转移方程
如果 s[i] == s[j]
i == j ，最长的回文子序列的长度为1
i +1 == j ，最长的回文子序列的长度为2
i + 1 < j ，现在 i + 1 -> j - 1 区间内找最长的，然后在加上 i j，最长的回文子序列的长度为dp[i + 1][j -1] + 2
如果s[i] != s[j]
i j 一定不可能同时存在构不成回文子序列，那就去找 i + 1 -> j 区间 和 i -> j - 1区间 找找，然后取两个区间的最大值就可以了。注意 i + 1 - > j - 1区间已经包括在上面的区间了，因此不用单独去找了。
3.初始化
因为 s[i] == s[j]情况分的特别细 ，所有dp[i+1][j-1]是不会越界的。
考虑一下 s[i] != s[j]，来一个二维dp表，我们只会用到上三角，因为要保证 i <= j。只有 i == j 并且 第一个位置 和 最后一个位置 dp[i][j-1] 和 dp[i+1][j] 会越界，但是注意 是在 i == j 的情况。因此我们可以在填表时提前特殊处理一下 i == j dp[i][j] =1。所以 dp[i][j-1] 和 dp[i+1][j]这两个位置越界根本不会发生，因此表无需初始化。
4.填表顺序
因此，从下往上填写每一行，每一行从左往右填写
5.返回值
dp[i][j] 表示：s 字符串 [i, j] 区间内的所有子序列，最长的回文子序列的长度。但是我们要的是整个区间的最长的回文子序列的长度，因此返回 dp[0][n-1]。
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i = n - 1; i >= 0; --i)// 枚举左端点 i
{
dp[i][i] = 1; // // 填表的时候初始化, i == j 特殊处理,下面填表就不会越界了
for(int j = i + 1; j < n; ++j)// 然后从 i + 1 的位置枚举右端点
{
// 分两种情况填写 dp 表
if(s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i][j - 1],dp[i + 1][j]);
}
}
// 返回结果
return dp[0][n -1];
}
};
6.让字符串成为回文串的最少插入次数
题目链接：1312. 让字符串成为回文串的最少插入次数
题目描述：
算法原理：
1.状态表示
我们已经做过很多回文串的问题，因此我们还是在这个 s 字符串中 选取一段区间
i ->j 研究问题 （i <= j）
dp[i][j] 表示：s里面 [i,j] 区间内的子串，使它成为回文串的最小插入次数
2.状态转移方程
关于回文串这里从i -> j，我们就以这两个端点来分析问题
当s[i] == s[j]
i == j，本身就是回文串，因此最小插入次数为0
i + 1 == j， i 和 j 相邻，最小插入次数也是0
i + 1 < j， i 和 j 中间有其他字符，因为 s[i] 已经等于 s[j]，所以只用考虑 i + 1 -> j -1区间最小插入次数，正好就是 dp[i + 1][j - 1]
当s[i] != s[j]
i 和 j 位置字符不相等，我想要让这个区间是回文串，必须得先让两个端点是回文串，有两个方法，第一种方法，可以考虑在 i 前面加一个 s[j] 然后就可以和 j 位置字符匹配， 然后让 i -> j -1区间成为回文串就行了，就是dp[i][j-1]。
第二种方法，可以考虑在 j 后面加一个 s[i] 然后就可以和 i 位置字符匹配， 然后让 i + 1-> j 区间成为回文串就行了，就是dp[i + 1][j]。
然后取这两种情况的最小值。
3.初始化
当 s[i] == s[j] 情况，分析一下dp[i + 1][j - 1] 会不会越界。
注意 i <= j 只填上三角，当 i == j 的时候对角第一个位置和最后一个位置会越界，但是 i == j 我们已经特殊处理了，i == j 等于 0。因此不用初始化。
还有一点 i + 1 == j ，可以和 i + 1 < j 合并，当 i + 1 == j 可以用dp[i + 1][j - 1] 填。如果在创建 dp 表 初始化就是0，i + 1 == j 放在i + 1 < j里面填，dp[i + 1][j - 1]也是0
当 s[i] != s[j]
肯定不会对角线，因为对角线肯定是 s[i] == s[j]。肯定是不会越界的。
4.填表顺序
当填 i j 发现会用到左边，左下，下边。因此从下往上每一行，每一行从左往右
5.返回值
dp[i][j] 表示：s里面 [i,j] 区间内的子串，使它成为回文串的最小插入次数，而我们要的是整个区间的最小插入次数，因此返回 dp[0][n-1]
class Solution {
public:
int minInsertions(string s) {
// 1.创建 dp 表
// 2.初始化
// 3.填表
// 4.返回值
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for(int i = n - 1; i >= 0; --i)
{
dp[i][i] = 0;
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][j - 1], dp[i + 1][j]) + 1;
}
}
return dp[0][n - 1];
}
};