目录
应用
应用1：Leetcode 647. 回文子串
题目
解题思路
动态规划
设 \(dp[i][j]\) 表示子串 \(s[i \cdots j]\) 是否是回文子串，若 \(dp[i][j] = True\)，则表示子串 \(s[i \cdots j]\) 是回文子串，否则，它就不是回文子串。假设字符串 \(s\) 的长度为 \(n\)。
边界条件
当子串 \(s[i \cdots j]\) 长度为 \(1\) 时，它是一个回文子串，因此边界条件如下：
\[dp[i][i] = True, \ 0 \le i \le n - 1 \]状态转移
对于字符串 \(s\)，我们倒序遍历子串的起始位置 \(i\)，同时使用指针 \(j\)，从位置 \(i+1\) 开始顺序枚举子串 \(s[i \cdots j]\) 的结束位置。
对于，任意一个子串 \(s[i \cdots j]\) ，存在两种情况，使得它是一个回文串：
-
子串长度为 \(1\)，即 \(i = j\)；
-
子串长度大于 \(1\)，若 \(s[i] = s[j]\)，且它的子串 \(s[i + 1 \cdots j - 1]\) 是一个回文串。
这里需要注意，当子串长度为 \(2\) ，即\(j = i + 1\) 时，它的子串 \(s[i + 1 \cdots j - 1]\) 是一个空串
""，需要单独讨论。
否则，它就不是一个回文串。
因此，状态转移方程为：
\[dp[i][j] = \begin{cases} (s[i] == s[j]) \land (j - i <= 1 \lor dp[i + 1][j - 1]) , & i \lt j\\ False, & otherwise \end{cases} \]这里，\(\land\) 表示逻辑与运算，\(\lor\) 表示逻辑或运算。
代码
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
result = 0
for i in range(n):
dp[i][i] = True
result += 1
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
dp[i][j] = (s[i] == s[j]) and (j - i <= 1 or dp[i + 1][j - 1])
if dp[i][j]:
result += 1
return result
简化之后的代码如下：
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
dp = [[False] * n for _ in range(n)]
result = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
result += 1
dp[i][j] = True
return result