回文串是从左到右和从右到左读起来一样的字符串，变种还有回文子序列，区别就是字符可以不连续。
求回文串个数、最长回文串、最长回文序列也是典型的二维动态规划问题。
我们通过几个简单的案例看一下这些题目的规律。
案例1：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
首先我们要明白：
①单个字符串肯定是回文串，
②两个字符，如果相同也是回文串
③超过三个字符序列的情况，如果最前最后两个字符相同，回文序列的长度就可以在去掉最前最后两个字符的回文序列+2
④如果最前最后两个字符串不相同，我们只好退其次，求解dp[i +1][j], dp[i][j - 1]两个的较大值
我们定义dp[i][j]为字符串中从i到j的最长回文子序列的长度，显而易见，dp[i][i]是回文的。
当s[i]==s[j]时，有dp[i][j] = dp[i + 1][j - 1] + 2
当s[i]!=s[j]时，有dp[i][j] = max{dp[i +1][j], dp[i][j - 1]}
我们要求的最终值就是dp[0][n-1]
为了保证求解当前问题是所有子问题已经求解，需要考虑遍历的顺序。
首先：因为i<=j,所有我们只需要求解上三角矩阵的值即可。
| i,j-1 | i,j | |
| i+1,j |
注意观察dp[i][j]的子问题，一个在自己的下方格子，一个在自己的左边格子，
也就是说我们的每一行的遍历要从下到上，每一列的遍历要从左到右。
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
//单个字符是回文的，长度为1
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i +1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
案例2：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
这个题目要求回文串，跟上一题目是有区别的，回文串必须是连续的。
遍历顺序还是一样行从下到上，列从左到有。
回文串要求最前最后两个字符必须相同，且取掉最前最后两个字符的子串仍然是回文串
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int ans = 0;
for (int i = n-1; i >=0; i--) {
for (int j = i; j < n; j++) {//j-i==0,单字符是回文串，j-i=1两个字符相等也是回文串
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
ans++;
}
}
}
return ans;
}
留一个未解题目
案例3（5）：给你一个字符串 s，找到 s 中最长的回文子串。