模版题-动态规划-最长回文子序列( 定义dp的含义 )
- 版权声明：本站原创文章，于2026-06-08，由 管理员 发表。
- 转载请注明： 模版题-动态规划-最长回文子序列( 定义dp的含义 ) | CodeGarden
```python
class Solution:
# 给你一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。
# 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
# 1 <= s.length <= 1000
def longestPalindromeSubseq(self, s: str) -> int:
# 在闭区间[i,j]内的字符串,回文子序列最长为dp[i][j]
n = len( s )
dp = [ [ 0 for _ in range( n ) ] for _ in range( n ) ]
for i in range( n ): dp[ i ][ i ] = 1
for i in range( n - 1, -1, -1 ):
for j in range( i + 1, n ):
if s[ i ] == s[ j ]:
# 首尾相等 在闭区间[i+1,j-1]中增加首尾
dp[ i ][ j ] = dp[ i + 1 ][ j - 1 ] + 2
else:
# 依次加入 s[i]和s[j] 取最大长度
dp[ i ][ j ] = max( dp[ i ][ j - 1 ], dp[ i + 1 ][ j ] )
return dp[ 0 ][ n - 1 ]
```