中等
提示
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

网友1：

回文子串：需要是数组内部连续的。

• dp数组含义：
  以i为起始，以j为结尾的子串是否为回文。
• 递推公式：
  当遍历到s【i】==s【j】时，就可以判断回文，有三种情况

1. a 此时i==j 一定是回文串
2. aa 此时 j-i=1 一定是回文串
   j-i<=1 : dp【i】【j】=True
3. aba 此时j-i>1 ，需要判断内部【 i+1，j-1】是否为回文串，如果是，那么合起来就是回文串。
   If dp【i+1】【j-1】==True; dp【i】【j】=True

• 初始化：
  由于上面提及了 i=j的情况，所以将所有位置初始化为false即可
• 遍历顺序：
  dp【i】【j】 需要依赖 dp【i+1】【j-1】,所以i从大到小，j从小到大，并且j为i后面，所以j从i开始遍历。
  
  
  
  

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。dp[i][j]要把i理解为左指针left，j要理解为右指针right，如上图所示。所以遍历顺序一点也不奇怪了，先把right指向第二个元素，下标为1，然后left一直从0开始，始终小于右指针。初始化呢，一开始开辟空间全都是0，所以也不用初始化了。这题建议也可以看看代码随想录的解题思路，它的遍历顺序需要注意。

// dp[i + 1][j - 1] 从递推公式可以看出dp[i][j] 依赖于dp[i + 1][j - 1]，所以要先算比较大的i,i要从末尾开始算，i--，j要从小的开始算，j++
class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) { // i 是 left
            for (int j = i; j < len; j++) { // j 是 right
                if (chars[i] == chars[j]) { // 当这俩相等时
                    if (j - i <= 1) { // 说明是同一个字符或者两个挨着的字符 
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 相隔超过两个字符
                        result++;
                        dp[i][j] = true;
                    }
                    // 其他情况都是false，初始化就为false，不用管了
                }
            }
        }
        return result;
    }
}