# \[647]\[中等]\[动态规划] 回文子串

## 题目描述

[647. 回文子串](https://leetcode-cn.com/problems/palindromic-substrings/)

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

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

示例 1：

```
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
```

示例 2：

```
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
```

提示：

* 输入的字符串长度不会超过 1000 。

## 解题思路

使用动态规划的思路, 参考[\[5\]\[中等\]\[动态规划\] 最长回文子串](https://kerasnoone.gitbook.io/garnet/suan-fa/zi-fu-chuan/broken-reference)中动态规划的解法.

```python
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)

        count = 0
        cache = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i - 1, -1):
                if j - i > 1:
                    cache[i][j] = s[j] == s[i] and cache[i + 1][j - 1]
                elif j - i == 1:
                    cache[i][j] = s[j] == s[i]
                elif j == i:
                    cache[i][j] = True
                if cache[i][j]:
                    count += 1
        return count
```