一、回文子串个数
647：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
dp[i][j]：s的区间[i,j]是否为回文串
class Solution {public int countSubstrings(String s) {int length = s.length();//s的区间[i,j]是否为回文串boolean[][] dp = new boolean[length][length];int res = 0;//dp[i][j]依赖于dp[i+1][j-1]，因此遍历顺序从下往上、从左往右for(int i =length-1;i>=0;i--){//j一定要大于等ifor(int j=i;j<length;j++){//dp[length-1][length-1]这时候赋值为true，下面不会出现越界if(s.charAt(i)==s.charAt(j)){if(j-i<=1){res++;dp[i][j]=true;}else if(dp[i+1][j-1]){res++;dp[i][j]=true;}}}}return res;}
}二、最长回文子序列
516：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
dp[i][j]：s的区间[i,j]最长回文序列长度
class Solution {public int longestPalindromeSubseq(String s) {int length = s.length();int[][] dp = new int[length][length];for(int i = 0;i<length;i++)dp[i][i]=1;for(int i=length-1;i>=0;i--){for(int j=i+1;j<length;j++){if(s.charAt(i)==s.charAt(j))dp[i][j]=dp[i+1][j-1]+2;elsedp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);}}return dp[0][length-1];}}三、最长回文子串
5：给你一个字符串 s，找到 s 中最长的回文子串。
dp[i][j]：s的区间[i,j]是否是回文串
class Solution {public String longestPalindrome(String s) {int length = s.length();if(length<2)return s;boolean[][] dp = new boolean[length][length];int start = 0;int end = 0;for(int i = length-1;i>=0;i--){for(int j=i;j<length;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1)dp[i][j]=true;elsedp[i][j]=dp[i+1][j-1];} if(dp[i][j]&&(j-i)>(end-start)){start=i;end = j;} }}return s.substring(start,end+1);}
}