对于回文子串问题，一般来说有三种方法来解决：
- 中心拓展算法 --》时间复杂度，空间复杂度
- 马拉车算法 --》时间复杂度 ，空间复杂度
- 动态规划 --》时间复杂度，空间复杂度
可以看出来其中马拉车算法综合而言是最优秀的，但是其实我们并不需要花太多时间去学马拉车算法，因为学习成本太高了，收益不大，并且马拉车算法的局限性很大，只适用于回文子串这类问题！
中心拓展算法这里我们也不讲，会把它放到其它算法章节中去讲，但其实它是比较简单的，看看源代码就能懂的！
我们主要讲的还是动态规划，为什么说时间复杂度和空间复杂度都这么高还要选动态规划呢，这是因为动态规划在我们后面遇到比较难的题的时候，可以化困难为简单，并且是通用的，能够把所有的子串是否回文等信息都保存到一个 dp 表里面，这就是优势所在！
1、回文子串（medium）
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"提示：
1 <= s.length <= 1000s由小写英文字母组成
解题思路
对于回文子串问题，一般来说我们都得用一个二维 dp 表来解决问题，因为我们需要遍历这个字符串里面的所有子串，那么就需要两个下标，分别是 i 和 j，这里规定 i <= j，并且每次循环时候，先固定 i，让 j 向后移动，这样子能得到所有的子串，如下图所示，画出了三种不同位置的情况，其中蓝色部分就是这个子串的内容：
所以状态表示我们也要用一个二维 dp 表来表示，其中 dp[i][j] 表示字符串中从 i 到 j 的子串，是否为回文串，如下图所示：
接下来就是状态转移方程，很明显，就是要判断是否构成回文子串，那么首先就得判断 s[i] 和 s[j] 是否相等，不相等的话直接就是 false 了，而如果相等的话还得分情况来讨论，如下图所示：
接下来就是初始化问题，其实这道题根本不用关心什么初始化问题，只需要全部初始化为 false 即可，为什么呢❓❓❓
因为会越界的情况就是在最后那种情况，也就是转化为判断 dp[i + 1][j - 1] 是否是回文子串那里，又因为这道题我们规定了 i <= j，那么此时实际上 dp 表我们只需要关注对角线以及对角线上方的内容即可，而 [i+1, j-1] 是当前位置的左下角，我们其实遍历开始是从倒数第二行开始的，根本不会说越界的情况，而对于左上角和右下角这两个位置，其实就是我们状态转移方程中判断 i == j 的这个情况，就不会用到左下角，因此不会越界！
然后就是遍历顺序问题，因为这道题用到左下角的元素，所以我们要推导右上角的元素，那么就得从下往上去遍历，而从左往右或者从右往左都是可以的！因为我们要用到左下角的值，所以要遍历到它，所以这里我们顺势采用从右往左去遍历比较直观！
最后就是返回值问题，因为这道题我们的 dp 表存的是 bool 值，true 代表是一个回文子串，所以我们只要遍历 dp 表，统计一下有多少个 true 然后返回即可！
class Solution {
public:
int countSubstrings(string s) {
// 创建二维dp表
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
// 从下往上，从右往左遍历
int ret = 0;
for(int i = n - 1; i >= 0; --i)
{
for(int j = n - 1; j >= i; --j)
{
// 不需要去关心false的情况，因为都初始化为false了
if(s[i] == s[j])
{
if(i == j || i + 1 == j)
dp[i][j] = true;
else
{
if(dp[i + 1][j - 1] == true)
dp[i][j] = true;
}
}
// 统计true的个数
if(dp[i][j] == true)
ret++;
}
}
return ret;
}
};2、最长回文子串（medium）
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
解题思路
这道题不过是上面那道题的变型而已，大体的思路和代码都是一样的，唯一不同的是我们更新不是上面那道题一样的次数，而是要一个最长回文串，那么我们就得记录下其长度和起始位置！
一开始我是在 dp 表下了手脚，将二维 dp 表的元素变成一个 pair，第一个元素装的是 bool 值表示 dp[i][j] 是否为回文子串，而第二个元素装的是 int 值表示的是从 i 到 j 的长度，然后大概也是按照和第一题的思路去做，虽然做出来了，但是时间耗时和空间消耗其实非常的大！
我仔细想了一下，就是因为装的元素是一个 pair，访问的时候和空间消耗自然就变大了许多，但是仔细一想好像根本不需要存从 i 到 j 的长度，因为我们已经有 i 和 j 的坐标了，直接拿 j - i + 1 不就得到了长度了吗！
所以把 dp 表改了一下，只需要表示当前的 dp[i][j] 是否为回文子串即可，而长度的任务交给 i 和 j 下标去计算就行了，然后用两个变量 maxlen 和 index 分别记录下最大长度和最大长度开始的下标即可，然后大体框架都是和上面代码一样的，这里就不细讲了， 具体可以参考上面。
最后返回字符串的截取部分即可！
class Solution {
public:
string longestPalindrome(string s) {
// 创建dp表
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int maxlen = 1; // 最大长度
int index = 0; // 最大长度的开始下标
for(int i = n - 1; i >= 0; --i)
{
for(int j = n - 1; j >= i; --j)
{
// 只有两个字符相等才继续判断
if(s[i] == s[j])
{
if(i == j || i + 1 == j)
dp[i][j] = true;
else
{
if(dp[i + 1][j - 1] == true)
dp[i][j] = true;
}
}
// 判断是否需要更新最值
if(dp[i][j] && j - i + 1 > maxlen)
{
maxlen = j - i + 1;
index = i;
}
}
}
return s.substr(index, maxlen);
}
};3、回文串分割IV（hard）
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。提示：
3 <= s.length <= 2000s只包含小写英文字母。
解题思路
这道题乍一看，是不是觉得好难，好像得去判断是否是回文子串的同时，还要用一个计数变量，统计当前是否为结尾的回文子串了，是否已经计数到 3 了……
确实，如果没有好思路这道题是比较难的，所以这里提供一种方法：
有没有想过，我们根本不需要去计数，因为字符串其实知道了中间的那个字符串，自然而然的就可以分为了三个字符串，如下所示：
只要我们有了 i 和 j 下标，然后判断这三个区间的子串是否是回文子串，是的话直接返回 true，如果遍历完所有的 i 和 j 的子串组合分割区间之后还是没有遇到三个区间的子串都是回文子串的，那么返回 false 即可！
而刚刚好我们之前的写过的回文子串问题，用一个二维 dp 表就完全把所有子串是否为回文子串已经全部保存起来了，我们只要去遍历这个处理完的 dp 表即可，也就相当于两次两层 for 循环，因为我们去判断三个区间是否是回文子串都是 O(1) 级别的访问，那么时间复杂度还是 O(n^2)，最重要的是这种解法非常的直观，写代码非常的简单！
而处理 dp 表的问题我们前两道题都已经讲过了，具体的可以参考上面的，这里就不细讲了！
最重要的越界问题，是在遍历 dp 表去判断三个区间的时候，因为我们用到了 dp[0][i - 1] 和 dp[j + 1][n - 1]，此时我们的 i 要从 1 开始遍历才行，不然从 0 开始的话会造成越界；同样，j 不能访问到 n - 1 下标，因为 j + 1 的话会变成 n，这时候也会越界！
注意越界问题，其它就没多大问题了！
class Solution {
public:
bool checkPartitioning(string s) {
// 创建dp表
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, false));
// 回文子串预处理
for(int i = n - 1; i >= 0; --i)
{
for(int j = n - 1; j >= i; --j)
{
if(s[i] == s[j])
{
if(i == j || i + 1 == j)
dp[i][j] = true;
else
if(dp[i + 1][j - 1] == true)
dp[i][j] = true;
}
}
}
// 判断[0, i-1] [i, j] [j+1, n-1]三个区间的子串是否都为回文串即可
// 注意下面i要从1开始防止i-1越界，j的终点不能到n-1，防止j+1越界
for(int i = 1; i < n; ++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（hard）
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2：
输入：s = "a"
输出：0示例 3：
输入：s = "ab"
输出：1提示：
1 <= s.length <= 2000s仅由小写英文字母组成
解题思路
这道题其实有点像之前写过的单词拆分那道题，大体思路都是差不多的！
首先是 状态表示 和 状态转移方程，如下图所示：
但是如果不优化的话，时间复杂度好像就是 ，因为首先得遍历变量 i，然后还有一个变量 j，就是两层循环，再加一层判断是否回文，就是三层循环，这样子时间复杂度就太大了，所以我们要优化一下！
优化思路其实和上面的题是一样的，也就是为了快速的得到当前的字符串区间是否是构成回文子串，那么我们之前已经做过了回文子串的题了，用一个二维的 dp 表保存了字符串的所有可能构成回文子串的信息，我们只需要先预处理一遍，将这个 dp 表构造出来，然后直接使用它，这样子时间复杂度就降为 ，还是比较可观的！
而处理 dp 表的问题我们第一道题都已经讲过了，具体的可以参考上面的，这里就不细讲了！
接下来就是初始化问题，我们是不怕越界的，虽然状态转移方程中涉及到了 dp[j - 1]，但是因为这是 0 < j <= i，是不会碰到 j == 0 的情况的，所以不会越界！最重要的问题是因为这道题用到了求最小值，那么我们的初始化就不能影响到求最小值，所以不能初始化为 0，应该全部初始化为无穷大，这样子才不会有干扰！
遍历顺序问题就比较简单，从左往右遍历就是了！
返回值的话，根据状态表示，我们要返回的就是 dp[n - 1] 也就是最后一个状态值！
class Solution {
public:
int minCut(string s) {
int n = s.size();
// 优化
vector<vector<bool>> assist(n, vector<bool>(n, false));
for(int i = n - 1; i >= 0; --i)
{
for(int j = n - 1; j >= i; --j)
{
if(s[i] == s[j])
{
if(i == j || i + 1 == j)
assist[i][j] = true;
else
if(assist[i + 1][j - 1] == true)
assist[i][j] = true;
}
}
}
// 创建dp表，初始化为无穷大
vector<int> dp(n, INT_MAX);
for(int i = 0; i < n; ++i)
{
if(assist[0][i] == true)
{
// 0~i构成回文串，不需要分割
dp[i] = 0;
}
else
{
// 0~i不构成回文串，那么就找j~i其中可能构成回文的子串
for(int j = i; j > 0; --j) // 注意j不能走到下标为0处
{
if(assist[j][i] == true)
{
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
};5、最长回文子序列（medium）
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。提示：
1 <= s.length <= 1000s仅由小写英文字母组成
解题思路
这道题又是一种比较新颖的定义 dp 表的方式，话不多说，直入主题。
首先 状态表示，根据 “经验 + 题目要求”，我们很快就能假定 dp[i] 表示以 i 结尾的所有子序列中，最长的回文子序列的长度。
接着就是 状态转移方程，仔细一想，如果要求一个子序列后面加上当前元素 s[i]，判断是否能构成一个新的并且更长的回文子序列，那就必须得知道前面那个子序列长什么样子，如果光光靠 dp[i - 1]、dp[i - 2]、…… 等状态，只能得到前面这些子序列的最大长度，并不足以帮助我们去判断是否能构成新的子序列，所以这种状态表示无疑是走不通的！
所以我们要换一种思路！一开始我想的是能不能记录下前面子序列最前面那个元素，和当前的 s[i] 进行对比，但其实这也是不行的，因为只知道首尾，是没办法判断中间部分是否依然会构成回文子序列的！
也就是说，关键点就是我们要知道构成这个回文子序列的样子是啥样！
所以 状态表示 我们可以先设定为：dp[i][j] 表示字符串 s 中 [i, j] 区间的所有子序列中，最长的回文子序列的长度！并且我们规定，i <= j。
接着就是 状态转移方程，分析如下图所示：
接着就是 初始化问题，因为我们状态转移方程分析的比较细，所以根本不需要初始化，也就相当于初始化为 0！比如 dp[i+1][j-1] 这个位置其实是不会越界的，因为我们要求 i <= j，并且前两个状态也就是重叠和相邻的时候的情况已经被我们考虑了，所以 i+1 和 j-1 是不可能会出现越界情况的！
然后就是 遍历顺序问题，因为我们这道题用到了三个位置来推导，分别是 dp[i + 1][j - 1]、dp[i][j - 1]、dp[i + 1][j]，这三个位置分别是当前位置的左下角、左边、下边三个位置，所以我们遍历要从下往上，从左往右遍历，才能从它们推导出当前位置的 dp 值。
最后就是 返回值问题，根据状态表示，我们要的是整个字符串中最长的回文子序列的长度，所以返回 dp[0][n - 1] 即可！
class Solution {
public:
int longestPalindromeSubseq(string s) {
// 创建dp表，初始化为0
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 从上往下，从左往右遍历
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
{
if(i == j)
dp[i][j] = 1;
else if(i + 1 == j)
dp[i][j] = 2;
else
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、让字符串成为回文串的最小插入次数（hard）
给你一个字符串 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] 表示以 i 结尾的所有子串中，插入元素成为回文串的最小插入次数，这样子表示的话是行不通的，因为我们既要知道尾，还得知道首，才能有递推关系！
所以状态表示为 dp[i][j] 表示字符串的从 i 到 j 区间中，插入元素成为回文串的最小插入次数，并且规定，i <= j。
下面来推导一下状态转移方程：
接着就是初始化问题，其实并不用我们去初始化，相当于全部初始化为 0，和前两道题是一样的情况，不会有越界出现的可能性，因为我们把状态划分的足够的细了！
遍历顺序问题，因为涉及到 dp[i + 1][j - 1]、dp[i][j - 1]、dp[i + 1][j]，分别是当前位置的左下角、左边和下边，所以遍历的时候要从下往上，从左往右！
返回值就是返回 dp[0][n - 1]。
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 从下往上，从左往右遍历
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
{
if(i + 1 < 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];
}
};