动态规划专题：回文串系列问题的深度解析与统一解法
动态规划专题：回文串系列问题的深度解析与统一解法
35.回文子串
回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
示例 1：
输入： s = “abc” 输出： 3 解释： 三个回文子串: “a”, “b”, “c”
示例 2：
输入： s = “aaa” 输出： 6 解释： 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示：
1 <= s.length <= 1000s由小写英文字母组成
动态规划能将所有的子串是否是回文的信息，保存在dp表里面
dp[i] [j]表示s字符串[i,j]的子串，是否为回文串
如果在s[i]=s[j]的情况下，dp[i+1] [j-1]的状态是true的话，那么就说明dp[i] [j]是true的
我们这里是不需要进行初始化操作的
这个题要求我们返回回文的个数，那么我们直接返回dp表中true的个数就行了
class Solution
{
public:
int countSubstrings(string s)
{
int n=s.size();
vector<vector<bool>>dp(n,vector<bool>(n));//nxn规模的矩阵
//dp[i][j] 是一个布尔值，用于表示子串 s[i...j] 是否是回文子串。
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;//如果i+1<j的话，那就说明子串的长度大于2，所以我们就得考虑(i+1,j-1)这个区间的dp值是否为true了，如果是true的话，那么dp[i][j]这段区域就是true的，但是如果我们的i+1等于y的话，就说明我们这段区域的长度是等于2的，并且两个字符还是相等的，所以我们就返回true就行了
//接着判断子串 s[i+1...j-1] 是否是回文。如果是回文，s[i...j] 也是回文；否则，如果 i+1 == j，即子串长度为 2，那么 s[i...j] 也是回文。
if(dp[i][j]==true)ret++;//每次 dp[i][j] == true 时，表示 s[i...j] 是回文子串，ret 就增加 1。
}
}
//循环结束之后整个dp表就保存着所有的子串的信息
return ret;
}
};i是往左边进行移动的，从最后一个位置开始的 j是往右边进行移动的
我们是从后面往前面进行遍历操作的，而不是从开头往后面的
这样，每次计算 dp[i][j] 时，已经可以保证 dp[i+1][j-1] 的结果已经计算出来了，从而可以正确判断子串 s[i...j] 是否是回文。
36.最长回文子串
最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入： s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。
示例 2：
输入： s = “cbbd” 输出：“bb”
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
这个题我们之前是使用中心扩展算法+双指针进行解决的，代码如下：
class Solution {
public:
string longestPalindrome(string s)
{
//中心扩展算法
int begin=0,len=0;//begin记录我们最终结果的起始位置，len记录我们最终的长度
for(int i=0;i<s.size();i++)//依次枚举所有的中点
{
//先做一次奇数长度的扩展
int left=i,right=i;
while(left>=0&&right<s.size()&&s[left]==s[right])
{
//满足上面的条件我们就让两个指针进行移动，
left--;
right++;
}
if(right-left-1>len) //更新下我们回文段串最长的长度
{
begin=left+1;//更新下我们回文段的有效位置的开始位置
len=right-left-1;
}
//偶数长度的扩展
left=i,right=i+1;
while(left>=0&&right<s.size()&&s[left]==s[right])
{
//满足上面的条件我们就让两个指针进行移动，
left--;
right++;
}
if(right-left-1>len)
{
begin=left+1;//更新下我们回文段的有效位置的开始位置
len=right-left-1;
}
}
//当这个for循环结束之后，那么begin就是存的是回文串的起始位置
return s.substr(begin,len);
}
};但是这里呢，我们使用动态规划进行问题的解决
判断子串是否是回文->用dp表，统计所有的子串是否是回文的信息->根据dp表起始位置得到我们想要的结果
dp[i] [j]表示：s[i] [j]的子串是否为回文串
dp里面值为true的情况下，长度最大的子串的起始位置以及长度 基本原理就是在每次判断完do[i] [j]为回文串之后，我们就进行长度的更新操作了 最后循环结束我们就得到了最后的长度，进行返回就行了
class Solution {
public:
string longestPalindrome(string s)
{
int n=s.size();
vector<vector<bool>>dp(n,vector<bool>(n));//大小是n*n的
//我们这里是不需要进行初始化操作的，我们能保证我们的数组不越界
//我们的循环是从后面开始进行操作的
int len=1,begin=0;//最小的长度肯定为1，起始的位置为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;
//如果此时的i+1<j的话，那么就说明此时的子串的长度大于2，那么我们就得去(i+1，j-1)这块区域寻找了
//如果i+1=j的话,那么就说明此时的子串长度就是2，那么就说明此时的子串是回文的，那么我们直接返回true就行了
}
//每填一个dp表我们就进行一个判断的操作
if(dp[i][j]==true&&j-i+1>len)//如果是回文的话并且我们的长度大于len
{
len=j-i+1;//更新我们的len的大小
begin=i;//更新我们最终返回的起始位置
}
}
}
return s.substr(begin,len);//直接返回从begin位置开始的len个长度的子串就行了
//这个就是我们的最长长度的回文串了
}
};37.分割回文串 IV
分割回文串 IV
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入： s = “abcbdd” 输出： true 解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。
示例 2：
输入： s = “bcbddxy” 输出： false 解释： s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000s 只包含小写英文字母。
我们只需要判断这三个区间是否为回文子串就行了
我们直接使用dp表保存所有的子串是否是回文的信息
class Solution
{
public:
bool checkPartitioning(string s)
{
int n=s.size();
vector<vector<bool>>dp(n,vector<bool>(n));//大小是n*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;
//如果此时的i+1<j的话，那么就说明此时的子串的长度大于2，那么我们就得去(i+1，j-1)这块区域寻找了
//如果i+1=j的话,那么就说明此时的子串长度就是2，那么就说明此时的子串是回文的，那么我们直接返回true就行了
}
}
}
//枚举所有的第二个字符串的起始位置和结束位置
for(int i=1;i<n-1;i++)//第二个字符串的区间是(1,n-2)
{
for(int j=i;j<n-1;j++)//这个是结束位置
{
if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1])//如果满足这三个dp都是true的话，那么就说明这段回文北分为三段回文了
{
return true;
}
}
}
//循环结束了，我们却没有返回，就说明没有切割成功
return false;
}
};就是先进行正常的回文信息记录 然后再填完了dp表之后，我们再分区域进行验证操作了
38.分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入： s = “aab” 输出： 1 解释： 只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2：
输入： s = “a” 输出： 0
示例 3：
输入： s = “ab” 输出： 1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
dp[i]表示：s[0,i]区间上的最长的子串，最少分割次数
如果(0，i)这个区间的串是回文的话，那么我们直接返回0就行了
但是如果不是回文的话 我们选择一个位置j，j的范围是0<j<=i的，就是最后一个子字符串的起始位置的下标 如果我们此时的(j,i)区间是回文的话，那么我们只需要查看(0,j-1)这个区间是否是回文的就行了 如果(j,i)区间是回文的话，那么我们直接dp[j-1]+1就行了
我们需要快速去判断(0,i)是否是回文的，(i,j)是否是回文的，所以我们这里是需要将回文的信息存放在dp中了
优化：二维dp表，将所有的子串是否是回文的信息，保存在dp表里面
初始化：将dp表中所有的值都初始化为无穷大就行了
返回dp(n-1)就行了，表示的是s[0,n-1]区间上的最长的子串，最少分割次数
class Solution
{
public:
int minCut(string s)
{
//预处理
int n=s.size();
vector<vector<bool>>isPal(n,vector<bool>(n));//判断是否是回文的dp表
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;
}
}
}
//两层循环下来之后，那么dp表里面就存放着这个字符串s的子串是否是回文的信息了
//这个dp就是计算最小的切割次数的
vector<int>dp(n,INT_MAX);//初始化为无穷大
for(int i=0;i<n;i++)
{
if(isPal[0][i]==true)dp[i]=0;//如果(0,i)是回文的话，说明我们是不需要切割的
else//就是说明(0,i)这个串不是回文，那么我们从中间找个点j进行遍历操作
{
for(int j=1;j<=i;j++)
if(isPal[j][i]==true)//如果(j,i)是回文的话，我们就得计算下dp(0,j-1)的值了，那么我们就更新下最小值
//dp[j-1] 是从 0 到 j-1 的最小切割次数
//加 1 是因为我们要在位置 j-1 处切割一次
dp[i]=min(dp[i],dp[j-1]+1);//计算下最小的分割次数
}
}
return dp[n-1];//直接返回(0,n-1)区间上回文串切割最小次数
}
};在这段代码中，dp[i]表示从0到i的子串所需的最小切割次数。初始化dp为INT_MAX的目的是为了确保在计算最小切割次数时，能够找到一个最小值。
就是正常进行isPal获取我们整个串的回文信息
然后再来一个dp，这个dp[i]表示的就是(0,i)区间上回文串的最少切割次数 如果(0,i)是回文的话，那么我们直接返回0就行了，因为整个串都是回文的，我们就不需要进行切割操作了
但是如果不是的话，那么我们中间找个点j，然后j就是最后一个子串的起始位置的下标 如果此时我们的isPal[j] [i]是true的话，就说明我们j到i这段是回文的，那么我们就更新下dp[i]了，看看我们此时的是dp[i]的值小还是dp[j-1]+1的值小 dp[j-1]+1就是从 0 到 j-1 的最小切割次数，加 1 是因为我们要在位置 j-1 处切割一次
39.最长回文子序列
最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入： s = “bbbab” 输出： 4 解释： 一个可能的最长回文子序列为 “bbbb” 。
示例 2：
输入： s = “cbbd” 输出： 2 解释： 一个可能的最长回文子序列为 “bb” 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
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--)
{
dp[i][i]=1;//就是dp[i][j]，i和j都是1的情况，结果就是1，下面我们就不需要额外去考虑了
for(int j=i+1;j<n;j++)
{
if(s[i]==s[j])
{
dp[i][j]=dp[i+1][j-1]+2;//直接考虑第三种，就是子串长度大于2，因为前面的两种情况都考虑过了
//i和j位置元素相等，那么我们就去(i+1，j-1)这段区间找最长的回文序列，+2就是加上了i和j的长度
}
else//就是这两个位置的数 是不相等的
{
//既然这两个位置的数不相等，那么我们就去(i+1,j)和(i,j-1)这两段区间找最大的回文序列
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][n-1];//直接返回(0,n-1)这段区间中最长的回文串子序列就行了
}
};40.让字符串成为回文串的最少插入次数
让字符串成为回文串的最少插入次数
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入： s = “zzazz” 输出： 0 解释： 字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入： s = “mbadm” 输出： 2 解释： 字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
示例 3：
输入： s = “leetcode” 输出： 5 解释： 插入 5 个字符后字符串变为 “leetcodocteel” 。
提示：
1 <= s.length <= 500s中所有字符都是小写字母。
dp[i] [j]表示：s里面[i,j]区间内的子串，使他成为回文串的最小插入次数
如果s[i]!=s[j]的话，那么有两种情况，一种就是我们在左边补上一个s[j]那么就和右边的j回文上了，那么我们就处理(i,j-1)这个区间就行了 但是如果我们是在右边补上一个s[i]的话，那么我们处理的就是[i+1,j]这个区间了 因为要求的是最小的插入次数，所以我们这里是需要在两种操作中求一个min值的
我们这里是不需要进行初始化操作的，因为我们这里分的很细致了
返回值就是dp[0] [n-1]
class Solution
{
public:
int minInsertions(string s)
{
int n=s.size();
vector<vector<int>>dp(n,vector<int>(n));
for(int i=n-1;i>=0;i--)
{
for(int j=i+1;j<n;j++)//我们直接从i+1的位置开始，因为当i=j的话，结果肯定是0的
{
if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];//两个字符相等，那么我们就得看看中间的区间是否需要插入字符形成回文了
//两个字符不相等，那么我们就先左边或者右边进行补齐
//如果从左边补s[j]的话，那么就和j消掉了，那么我们检查的就是(i,j-1)这个区间了
//反之就是(i+1,j)这个区间了
else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;//直接从这两个区间找最小值
//最后+1的操作就是要么加的是左边的字符，要么加的是右边的字符
}
}
return dp[0][n-1];
}
};还是正常的操作，先将信息存在dp表中 如果i和j两个字符相等的话，那么我们的结果就是在中间的区间(i+1,j-1)里面了
但是如果不相等的话，那么我们就得从两种补齐方式种求出最小值了
腾讯云开发者
