算法进阶：动态规划在回文串问题中的核心思想与实践
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>dp(n,vector(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=0&&rightlen) //更新下我们回文段串最长的长度 { begin=left+1;//更新下我们回文段的有效位置的开始位置 len=right-left-1; } //偶数长度的扩展 left=i,right=i+1; while(left>=0&&rightlen) { 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>dp(n,vector(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+1len)//如果是回文的话并且我们的长度大于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>dp(n,vector(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
分割回文串 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>isPal(n,vector(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就是计算最小的切割次数的 vectordp(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>dp(n,vector(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>dp(n,vector(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)里面了
但是如果不相等的话，那么我们就得从两种补齐方式种求出最小值了
