题解 | #最长回文子序列#

二维 dp 问题; 设置 二维 dp， dp[i][j] 表示 以 i 为开始, j 为结束的回文子序列的最长长度; 当 s[i] = s[j] 时, dp[i][j] 由 dp[i + 1][j - 1] 转移过来 + s[i] 和 s[j] 的长度 2 当 s[i] != s[j] 时, dp[i][j] 由 dp[i + 1][j] 或 dp[i][j + 1] 中较大的一个转移而来,因为取的是最大值. 初始值, dp[i][i] = 1 i < len(s) 代码如下:

import sys
s = sys.stdin.readline().strip()
n = len(s)
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 1
# 因为根据已有状态推出当前状态 dp[i][j] 从 dp[i + 1][j] 和 dp[i + 1][j], dp[i][j - 1] 转移,则采用从后往前,从左往右的方式
# 后 -> 前
for i in range(n - 1, -1, -1):
    # 左 -> 右
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j - 1] + 2
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
print(dp[0][-1])