模版题-动态规划-回文子串( 定义回文子串的dp含义 )
- 版权声明：本站原创文章，于2026-06-08，由 管理员 发表。
- 转载请注明： 模版题-动态规划-回文子串( 定义回文子串的dp含义 ) | CodeGarden
```python
class Solution:
# 给你一个字符串s，请你统计并返回这个字符串中回文子串的数目。
# 回文字符串是正着读和倒过来读一样的字符串。
# 子字符串是字符串中的由连续字符组成的一个序列。
# 1 <= s.length <= 1000
# s 由小写英文字母组成
def countSubstrings(self, s: str) -> int:
# 子字符串的所有情况: [ i ][ j ]二维数组i,j的所有排列
# dp[i][j]表示区间[i,j]是否为回文子串( 左闭右闭区间 )
# 若判断[i,j]是否回文,依赖于[ i+1, j-1 ]是否回文( 即在子串基础上判断首尾是否相等 )
n = len( s )
dp = [ [ False for _ in range( n ) ] for _ in range( n ) ]
ans = 0
# 倒序:递推公式中使用了dp[ i+1 ]
for i in range( n - 1, -1, -1 ):
for j in range( i, n ):
# 对角线 or 回文子串相同
if s[ i ] == s[ j ] and ( j - i <= 1 or dp[ i + 1 ][ j - 1 ] ):
dp[ i ][ j ] = True
ans += 1
return ans
```