引言：
回文字符串 是正着读和倒过来读一样的字符串。
动态规划的回文串问题一般是把子串是否是回文串的信息保持在dp表里面，所以更多的时候回文串的dp表只是起到一个辅助的作用，有一些题要利用回文串dp表再做一次动态规划，其实很多困难题某一些步骤都是可以动态规划来化简的。😎😎😎
例题1：回文子串
链接：回文子串
题目简介：
给你一个字符串
s
，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
解法（动态规划）：
当然这题的最优解不是动态规划而是中心拓展算法，但是我们这里主要叙述动态规划。
这一题其实就是一个把回文子串信息保存在dp表里面的模板题😎
对于本题我们可以先预处理⼀下，将所有子串是否回⽂的信息统计在dp 表⾥⾯，然后直接在表里面统计true 的个数即可。
1. 状态表示：
dp[i][j] 表示： s 字符串[i, j] 的子串，是否是回文串。
这个二维的dp表其实只需用到上三角的地方，因为j是大于等于i的。
** 2.状态转移方程：**
对于回文串，我们⼀般分析⼀个区间两头的元素：例如下图利用最外层和内层的递推关系完成动态规划。
**（1）当s[i] != s[j] 的时候：不可能是回文串， dp[i][j] = 0 ； **
（2）当s[i] == s[j] 的时候：根据长度分三种情况讨论：
1.⻓度为1 ，也就是i == j ，此时⼀定是回文串， dp[i][j] = true。
2.⻓度为2 ，也就是i + 1 == j ：此时也⼀定是回⽂串， dp[i][j] = true 。
3.⻓度⼤于2 ，此时要去看看[i + 1, j - 1] 区间的子串是否回文： dp[i][j] = dp[i + 1][j - 1] 。
** 3.初始化：**
无需初始化，因为我们填表的范围如下图，会越界的节点在对角线，但是我们上面的状态转移方程已经把i == j的情况特判了，所以不会越界。
** 4.填表顺序：**
从下往上
** 5.返回值：**
返回dp 表中true 的个数。
代码如下：
dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;解释如下：因为i == j 和i + 1 == j 的情况下dp[i][j]都为true，长度大于2对应i + 1 < j 的情况。
class Solution {
public int countSubstrings(String ss) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = ss.length();
char[] s = ss.toCharArray();
boolean[][] dp = new boolean[n][n];
int count = 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] == true){
count++;
}
}
}
return count;
}
}
时间复杂度：O（n^2）
空间复杂度：O（n^2）
下面我给出一题大家练练手，解法过程和例题1差不多就是最后创建完回文dp表最后的返回值不一样。最长回文子串
例题2：回文串分割IV
链接：回文串分割IV
题目简介：
给你一个字符串
s
，如果可以将它分割成三个 非空 回文子字符串，那么返回
true
，否则返回
false
。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
关于预处理所有子串是否回文，已经在上⼀道题目里面讲过，这里就不再赘述啦~
先把回文dp表填好，接下来枚举三个子串除字符串端点外的起止点，查询这三段非空子串是否是回文串。 枚举i和j这两条分界线即可，注意区间的闭合问题和J必须要大于等于i。
代码如下：
利用 dp 处理⼀下所有的子串是否回文。
枚举第二个字符串所有的起始位置和终止位置。
写代码希望大家按照1.创建 dp 表2，初始化，3.填表，4.返回值的顺序来进行书写代码，这样不会乱。
class Solution {
public boolean checkPartitioning(String s) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = s.length();
boolean[][] dp = new boolean[n][n];
for(int i = n - 1;i >= 0;i--){
for(int j = i;j < n;j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
}
}
}
boolean ans = false;
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]){
ans = true;
return ans;
}
}
}
return false;
}
}
时间复杂度：O（n^2）
空间复杂度：O（n^2）
例题3：分割回文串II
链接：分割回文串II
题目简介：
给你一个字符串
s
，请你将
s
分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
解法（动态规划）：
1. 状态表示：
dp[i] 表示： s中[0, i] 区间上的字符串，最少分割的次数。
** 2.状态转移方程：**
状态转移方程⼀般都是根据最后⼀个位置的信息来分析：设0 <= j <= i ，那么我们可以根据j ~ i位置上的子串是否是回文串分成下面两类：
（1）当[j ,i] 位置上的子串能够构成⼀个回文串，那么dp[i] 就等于[0, j - 1] 区间上最少回文串的个数+1，即dp[i] = dp[j - 1] + 1 。
（2）当[j ,i] 位置上的⼦串不能构成⼀个回文串，此时j 位置就不⽤考虑。
由于我们要的是最小值，因此应该循环遍历⼀遍j的取值，拿到里面的最小值即可。
优化：我们在状态转移⽅程里面分析到，要能够快速判读字符串里面的⼦串是否回文。因此，我们 可以先处理⼀个dp 表，里面保存所有⼦串是否回文的信息。
** 3.初始化：**
为了防止求min操作时，0干扰结果。我们先把表里面的值初始化为无穷大。
** 4.填表顺序：**
从左往右
** 5.返回值：**
应该返回dp[n - 1]。
代码如下：
其中algorithm就是回文串信息的dp表。
class Solution {
public int minCut(String s) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = s.length();
int[] dp = new int[n];
boolean[][] algorithm = new boolean[n][n];
for(int i = n - 1;i >= 0;i--){
for(int j = i;j < n;j++){
if(s.charAt(i) != s.charAt(j)){
algorithm[i][j] = false;
}else{
algorithm[i][j] = i + 1 < j ? algorithm[i + 1][j - 1] : true;
}
}
}
for(int i = 0;i < n;i++){
dp[i] = 0x3f3f3f3f;
}
for(int i = 0;i < n;i++){
for(int j = 0;j <= i;j++){
if(algorithm[0][i]){
dp[i] = 0;
break;
}else{
if(algorithm[j][i]){
dp[i] = Math.min(dp[i],dp[j - 1] + 1);
}
}
}
}
return dp[n - 1];
}
}
时间复杂度：O（n^2）
空间复杂度：O（n^2）
例题4：最长回文子序列
链接：最长回文子序列
题目简介：
给你一个字符串
s
，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
** 解法（动态规划）：**
1. 状态表示：
回文串问题一般取左右区间，以左右节点来分析。
dp[i][j] 表示：s字符串[i, j] 区间内的所有的子序列中，最长的回文子序列的长度。
** 2.状态转移方程：**
关于回文子序列和回文子串的分析⽅式，⼀般都是⽐较固定的，都是选择这段区域的左右端点的字符情况来分析。因为如果⼀个序列是回文串的话，去掉⾸尾两个元素之后依旧是回⽂串，⾸尾加上两个相同的元素之后也依旧是回文串。因为，根据首尾元素的不同，可以分为下面两种情况：
（1）当首尾两个元素相同的时候，也就是s[i] == s[j] ：那么[i, j] 区间上的最长回文子序列，应该是[i + 1, j - 1] 区间内的那个最长回文子序列首尾填上s[i] 和s[j] ，此时dp[i][j] = dp[i + 1][j - 1] + 2 。
（2）当首尾两个元素不相同的时候，也就是s[i] != s[j] ：此时这两个元素就不能同时添加在⼀个回⽂串的左右，那么我们就应该让s[i] 单独加在⼀个序列的左边，或者让s[j] 单独放在⼀个序列的右边，看看这两种情况下的最大值：
1.单独加⼊s[i] 后的区间在[i, j - 1] ，此时最长的回⽂序列的长度就是dp[i] [j - 1] 。
2.单独加⼊s[j] 后的区间在[i + 1, j] ，此时最长的回⽂序列的长度就是dp[i + 1][j] 。
取两者的最大值，于是dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。
**综上所述，状态转移方程为： **
（1）当s[i] == s[j] 时： dp[i][j] = dp[i + 1][j - 1] + 2 .
（2）当s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) .
** 3.初始化：**
根据状态转移⽅程dp[i][j] = dp[i + 1][j - 1] + 2 ，我们状态表⽰的时候，选取的是⼀段区间，因此需要要求左端点的值要⼩于等于右端点的值，因此会有两种边界情况：
（1）当i == j 的时候， i + 1 就会大于j - 1 ，此时区间内只有⼀个字符。这个⽐较好分析， dp[i][j] 表示⼀个字符的最长回文序列，⼀个字符能够自己组成回文串，因此此时dp[i][j] = 1。
（2）当i + 1 == j的时候， i + 1 也会大于j - 1 ，此时区间内有两个字符。这样也好分析，当这两个字符相同的时候， dp[i][j] = 2 ；不相同的时候， d[i][j] = 0.
对于第⼀种边界情况，我们在填表的时候，就可以同步处理。
对于第⼆种边界情况， dp[i + 1][j - 1] 的值为0 ，不会影响最终的结果，因此可以不用考虑。
** 4.填表顺序：**
从下往上填写每⼀行。
每⼀行从左往右。
** 5.返回值：**
根据状态表示，我们需要返回[0, n -1] 区域上的最长回文序列的长度，因此需要返回dp[0][n - 1] 。
代码如下：
class Solution {
public int longestPalindromeSubseq(String s) {
//.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = s.length();
int[][] dp = new int[n][n];
for(int i = n - 1;i >= 0;i--){
//j必须要大于等于i
for(int j = i;j < n;j++){
if(s.charAt(i) == s.charAt(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] = Math.max(dp[i][j - 1],dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
}
时间复杂度：O（n^2）
空间复杂度：O（n^2）
例题5：让字符串成为回文串的最小插入次数
链接：让字符串成为回文串的最小插入次数
题目简介：
给你一个字符串
s
，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让
s
成为回文串的 最少操作次数 。
回文串是正读和反读都相同的字符串。
** 解法（动态规划）：**
1. 状态表示：
状态表示： dp[i][j]表示字符串[i, j] 区域成为回文子串的最少插入次数。
** 2.状态转移方程：**
根据首尾元素的不同，可 以分为下⾯两种情况：
（1）当首尾两个元素相同的时候，也就是s[i] == s[j] ：
1.那么 [i, j] 区间内成为回文子串的最少插⼊次数，取决于[i + 1, j - 1] 区间内成为回文子串的最少插入次数。
2.若 i == j 或i == j - 1（ [i + 1, j - 1] 不构成合法区间），此时只有1 ~2个相同的字符， [i, j] 区间⼀定是回文子串，成为回文子串的最少插入次数是0.
（2）当首尾两个元素不相同的时候，也就是s[i] != s[j] ：
1.此时可以在区间最右边补上⼀个 s[i] ，需要的最少插入次数是 [i + 1, j] 成为回文子串的最少插⼊次数+本次插入，即 dp[i][j] = dp[i + 1][j] + 1 。
2.此时可以在区间最左边补上⼀个 s[j] ，需要的最少插入次数是 [i, j + 1] 成为回文子串的最少插⼊次数+本次插⼊，即 dp[i][j] = dp[i][j + 1] + 1 。
综上所述，状态转移方程为：
（1）当s[i] == s[j]时： dp[i][j] = i >= j - 1 ? 1 : dp[i + 1][j - 1]。
（2）s[i] != s[j]时： dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1 。
** 3.初始化：**
没有不能递推表示的值，无需初始化。
** 4.填表顺序：**
从下往上填写每⼀行
从下往上填写每⼀行
** 5.返回值：**
返回dp[0][n - 1]。
代码如下：
class Solution {
public int minInsertions(String s) {
//1.创建 dp 表
//2.初始化
//3.填表
//4.返回值
int n = s.length();
int[][] dp = new int[n][n];
for(int i = n - 1;i >= 0;i--){
for(int j = i;j < n;j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : 0;
}else{
dp[i][j] = Math.min(dp[i + 1][j] + 1,dp[i][j - 1] + 1);
}
}
}
return dp[0][n - 1];
}
}
时间复杂度：O（n^2）
空间复杂度：O（n^2）
结语：
其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。
版权归原作者 gobeyye 所有， 如有侵权，请联系我们删除。