一 题目：
二 思路：
动态规划法
- 状态：dpi 表示字符串s在i,j区间的子串是否是一个回文串。 状态转移方程：当 si == sj && (j - i < 2 || dpi 1) 时，dpi=true，否则为false 这个状态转移方程是什么意思呢？
- 当只有一个字符时，比如 a 自然是一个回文串。
- 当有两个字符时，如果是相等的，比如 aa，也是一个回文串。
- 当有三个及以上字符时，比如 ababa 这个字符记作串 1，把两边的 a 去掉，也就是 bab 记作串 2，可以看出只要串2是一个回文串，那么左右各多了一个 a 的串 1 必定也是回文串。所以当 si==sj 时，自然要看 dpi 1 是不是一个回文串。
三 代码：
代码语言：javascript复制class Solution {
public int countSubstrings(String s) {
int len = s.length();
int res=0;
//如dp[i][j]存储i~j是否是回文字符串
boolean [][] dp=new boolean[len][len];
for (int j = 0; j < len; j ) {
for (int i = 0; i <= j; i ) {
if (s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i 1][j-1])){
dp[i][j]=true;
res ;
}
}
}
return res;
}
}也可以用中心法。这个我之前写过，可以参考参考https://cloud.tencent.com/developer/article/1923972
