字符串中有多少个回文子串。

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

• 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc”

输出：3

解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：“aaa”

输出：6

解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

• 算法思路

1.求一个字符串中有多少个回文子串，子串必须是连续的，子序列可以不连续，那我定义dp[i][j]：表示字符串s从下标i到j是否是回文串，如果dp[i][j]是true，则表示是回文串，否则不是回文串。这题可以使用考虑动态规划来解决。

（正在学习动态规划思想，就当练练手，做个笔记，用Java做一次）

2. 那么如果我要知道dp[i][j]是否为true我还要计算dp[i+1][j-1]是否为回文串

3. 那么我再想根据题目的条件当i和j离得非常近的时候，比如j-i<=2的话，这时的dp[i][j]也是回文子串

分析到此处，咋们也就大概能写出个地推公式了：

s.charAt(i) != s.charAt(j)) 
    continue;
dp[i][j] = (j-i <= 2 || dp[i+1][j-1]);      

for(int i=length-1;i>=0;i--) {
  for(int j=i;j<=length;j++) {//保证i<=j
    if(s.charAt(i) != s.charAt(j)) {//首先得是保证两端相等
      continue;
    }
    dp[i][j] = (j-i <= 2 || dp[i+1][j-1]);//r
  }
}      

import java.util.Scanner;
public class 回文子串个数 {

  public static void main(String[] args) {
    Scanner val = new Scanner(System.in);
    String s = val.next();
    System.out.println(s);
    System.out.println(countSubstrings(s));

  }
  static int countSubstrings(String s) {
    int count=0;
    int length = s.length();//获取字符串的长度
    boolean[][] dp = new boolean[length][length];
    for(int i=length-1;i>=0;i--) {
      for(int j=i;j<length;j++) {
        if(s.charAt(i) != s.charAt(j)) {//首先得是保证两端相等
          continue;
        }
        dp[i][j] = (j-i <= 2 || dp[i+1][j-1]);//r
        if(dp[i][j]) {
          count++;
        }
      }
    }
    return count;
  }
}