目录
回文子串
解法一【中心扩散法】
解法二【动态规划法】
最长回文子串
分割回文串IV
分割回文串II
最长回文子序列
让字符串成为回文串的最少插入次数
声明：下面的讲解，主要采用动态规划法来解决！！！
回文子串
题目
思路
判断一个字符串是否是回文的，我们很容易想到中心扩散法，从字符串中间向两端扩散或者两头向中间收拢，还可以采用动态规划来解决，下面将介绍两种方法来解决这道题。
解法一【中心扩散法】
通过穷举所有可能的情况，并判断该字符串是否是回文串。
代码
class Solution {
public:int sum=0;int countSubstrings(string s) {helper(s,0);return sum;}void helper(string s,int start){if(start==s.size()) return;for(int i=start;i<s.size();i++){if(isPalindrome(s,start,i)){sum++;}}helper(s,start+1);}bool isPalindrome(string s,int l,int r){while(l<r){if(s[l++]!=s[r--])return false;}return true;}
};解法二【动态规划法】
状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。
状态转移方程：
初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。
填表顺序：从下往上。
我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。
代码
class Solution {
public:int sum=0;int countSubstrings(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//dp[i][j]=dp[i+1][j-1]for(int i=n-1;i>=0;i--)for(int j=n-1;j>=i;j--){if(s[i]!=s[j]) dp[i][j]=false;else{if(i==j) dp[i][j]=true;else if(i+1==j) dp[i][j]=true;elsedp[i][j]=dp[i+1][j-1];}}for(int i=0;i<n;i++)for(int j=i;j<n;j++)if(dp[i][j]) sum++;return sum;}
};最长回文子串
题目
思路
和上一道题一样，我们需要穷举出该字符串所有子串的情况，并判断是否是回文串，而且需要记录是回文串的起始位置和长度，便于找出最长回文子串，如果采用中心扩散法，时间复杂度是O(N^3)，可能会超时，但经过我尝试，这种方法的确会超时。所以下面我们采用动态规划，穷举出该字符串所有子串的情况，并判断是否是回文串，时间复杂度是O(N^2)，不会超时。
解法
状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。
状态转移方程：
初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。
填表顺序：从下往上。
我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。
代码
class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//dp[i][j]=dp[i+1][j-1]for(int i=n-1;i>=0;i--)for(int j=n-1;j>=i;j--){if(s[i]!=s[j]) dp[i][j]=false;else{if(i==j) dp[i][j]=true;else if(i+1==j) dp[i][j]=true;elsedp[i][j]=dp[i+1][j-1];}}int len=1,pos=0;for(int i=0;i<n;i++)for(int j=i;j<n;j++)if(dp[i][j] && j-i+1>len){len=j-i+1;pos=i;}return s.substr(pos,len);}
};分割回文串IV
题目
思路
其实解法就是我们找到两个位置，将字符串分割为三段区间，并且满足三段区间都是回文串即可，如果采用中心扩散法，分析可知时间复杂度是O(N^3)，可能会超时，所以接下来，我们依旧采用一种算是“一劳永逸”的解法，动态规划，我们会觉得这道题不是困难题了，而是so easy。
解法
状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。
状态转移方程：
初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。
填表顺序：从下往上。
我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。
代码
class Solution {
public:bool checkPartitioning(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));//dp[i][j]=dp[i+1][j-1]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;}//[0,i-1] [i,j] [j+1,n-1]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
题目
思路
我们可以尝试以某个位置为结尾，并判断[0,i]区间是否是回文串，如果是的话，这段区间的最少分割次数就是0，如果不是的话，需要分情况讨论。
先声明一点，下面我依旧先使用动态规划穷举出所有可能的子字符串，下一步还会使用动态规划，这样的话，就会两使用dp来表示，肯定是不可以的，但是基于前一步的动态规划在前几道题已经讲过，所以这里就不再重新画图了，把前面的图拿过来直接使用了！！！！
状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。
状态转移方程：
初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。
填表顺序：从下往上。
我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。
填表顺序：从下往上。
状态表示：dp[i]表示以i位置为结尾，使[0,i]区间的字符串成为回文子串的最少分割次数。
填表顺序：从左往右。
代码
class Solution {
public:int minCut(string s) {int n=s.size();vector<vector<bool>> isP(n,vector<bool>(n));//dp[i][j]=dp[i+1][j-1]for(int i=n-1;i>=0;i--)for(int j=i;j<n;j++){if(s[i]==s[j])isP[i][j]=i+1<j?isP[i+1][j-1]:true;}vector<int> dp(n,0x3f3f3f3f);//dp[i] 表示从0到i最少分割次数for(int i=0;i<n;i++){if(isP[0][i]) dp[i]=0;else{for(int j=i;j>0;j--)if(isP[j][i]) dp[i]=min(dp[j-1]+1,dp[i]);}}return dp[n-1];}
};最长回文子序列
题目
思路
如果我们依旧采用以某个位置为结尾来分析问题，会发现推不出状态转移方程，下面尝试采用以某一段区间来进行分析本题。
状态表示：dp[i,j]表示[i,j]区间内最长的回文子序列长度。
状态转移方程：
填表顺序：从下往上，从左往右。
代码
class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));//dp[i][j] 表示[i,j]区间最长回文子序列长度for(int i=n-1;i>=0;i--){dp[i][i]=1;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][j-1],dp[i+1][j]);}}return dp[0][n-1];}
};让字符串成为回文串的最少插入次数
题目
思路
如果我们依旧采用以某个位置为结尾来分析问题，会发现推不出状态转移方程，下面我们尝试采用以某一段区间来进行分析本题。
状态表示：dp[i,j]表示让[i,j]区间字符串成为回文串的最少插入次数。
状态转移方程：
填表顺序：从下往上，从左往右。
代码
class Solution {
public:int minInsertions(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));//dp[i][j]表示[i,j]区间称为回文串的最少插入次数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];}
};
