代码随想录算法训练营第四十天 | 动态规划 Part13

468 字

2 分钟

代码随想录算法训练营第四十天 | 动态规划 Part13

2025-07-26

算法

动态规划、回文子串问题

/

LeetCode

/

Python

647. 回文子串#

LeetCode 647. Palindromic Substrings

解题思路

使用二维动态规划数组 dp[i][j] 表示子串 s[i:j+1] 是否为回文。
初始化时，所有单个字符均为回文子串，dp[i][i] = True。
状态转移：
- 若 s[i] == s[j]，且
  - 子串长度为 1 或 2 (j - i <= 1)，则为回文。
  - 否则取决于 dp[i+1][j-1] 是否为回文。
遍历顺序：i 从后往前遍历，j 从 i 往后遍历。

1
class Solution:
2
    def countSubstrings(self, s: str) -> int:
3
        n = len(s)
4
        dp = [[False] * n for _ in range(n)]
5
        res = 0
6
        # 单个字符是回文子串
7
        for i in range(n):
8
            dp[i][i] = True
9
            res += 1
10
        # 从后向前遍历 i，保证转移时 dp[i+1][j-1] 已计算
11
        for i in range(n - 1, -1, -1):
12
            for j in range(i + 1, n):
13
                if s[i] == s[j]:
14
                    if j - i == 1 or dp[i + 1][j - 1]:
15
                        dp[i][j] = True
16
                        res += 1
17
        return res

516. 最长回文子序列#

LeetCode 516. Longest Palindromic Subsequence

解题思路

使用二维动态规划数组 dp[i][j] 表示子串 s[j:i+1] 的最长回文子序列长度。
初始化时，所有单个字符长度为 1。
状态转移：
- 若 s[i] == s[j]，则 dp[i][j] = dp[i - 1][j + 1] + 2，即包含 s[i] 和 s[j] 两个字符加上中间子串的最长回文子序列长度。
- 否则，取舍去 s[i] 或 s[j] 后的最大值： dp[i][j] = max(dp[i - 1][j], dp[i][j + 1])。
遍历顺序：
- i 从前向后，j 从 i-1 向前遍历，保证访问状态正确。

1
class Solution:
2
    def longestPalindromeSubseq(self, s: str) -> int:
3
        n = len(s)
4
        dp = [[0] * n for _ in range(n)]
5
        # 单字符最长回文长度为 1
6
        for i in range(n):
7
            dp[i][i] = 1
8
        # i 右边界从小到大遍历
9
        for i in range(1, n):
10
            # j 左边界从 i-1 向前遍历，保证 j < i
11
            for j in range(i - 1, -1, -1):
12
                if s[i] == s[j]:
13
                    dp[i][j] = dp[i - 1][j + 1] + 2
14
                else:
15
                    dp[i][j] = max(dp[i - 1][j], dp[i][j + 1])
16
        # 最大值一定在最后一行
17
        return max(dp[n - 1])