# \[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\]\[中等\]\[动态规划\] 最长回文子串](/garnet/suan-fa/dong-tai-gui-hua/5-zui-chang-hui-wen-zi-chuan.md)中动态规划的解法.

```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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/647-hui-wen-zi-chuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.