回文串是从左到右和从右到左读起来一样的字符串，变种还有回文子序列，区别就是字符可以不连续。
求回文串个数、最长回文串、最长回文序列也是典型的二维动态规划问题。
我们通过几个简单的案例看一下这些题目的规律。
案例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 中最长的回文子串。
原文地址：http://www.cnblogs.com/wangbin2188/p/16847580.html
