题目地址：https://leetcode-cn.com/probl…题目描述：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例 1:输入: “abc"输出: 3解释: 三个回文子串: “a”, “b”, “c”.示例 2:输入: “aaa"输出: 6说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.注意:输入的字符串长度不会超过1000。解答：这一题可以用穷举法，检查s[i…j]是否为回文字串但是应该会超时。不过我们可以这么想，如果现在知道了s[i…j]是回文字串，那么如果s[i-1] == s[j+1]，那么s[i-1…j+1]也一定是回文字串。这样就联想到了动态规划。设置dp[i] [j]表示s[i…j]是否是回文字串，若是为true，否则为false。那么对任意的dp[i] [j] = dp[i+1] [j-1]&&s[i]==s[j]。一旦为true就把结果+1。不过需要注意的是要使用上述的递推公式，需要先求出所有长度为1和为2的回文字串，这个比较简单，就不赘述了。java ac代码：class Solution { public int countSubstrings(String s) { //dp[i][j]表示s[i…j]是否为回文字串。 boolean[][] dp = new boolean[s.length()][s.length()]; int ans = 0; for(int i = 0;i < dp.length;i++) { dp[i][i] = true; ans++; } for(int i = 1;i < dp.length;i++) if(s.charAt(i-1) == s.charAt(i)) { dp[i-1][i] = true; ans++; } for(int k = 2;k < s.length();k++) for(int i = k;i < s.length();i++) if(s.charAt(i-k) == s.charAt(i)&&dp[i-k+1][i-1]) { dp[i-k][i] = true; ans++; } return ans; }}