0516. 最长回文子序列 #
- 标签:字符串、动态规划
- 难度:中等
题目大意 #
给定一个字符串 s
,找出其中最长的回文子序列,并返回该序列的长度。
解题思路 #
动态规划求解。
定义状态 dp[i][j]
表示为:字符串 s
在 [i, j]
范围内的最长回文子序列长度。
则状态转移公式为:
-
如果
s[i] == s[j]
,则dp[i][j]
为[i + 1, j - 1]
范围内最长回文子序列长度 + 2,即dp[i][j] = dp[i + 1][j - 1] + 2
。 -
如果
s[i] != s[j]
,则dp[i][j]
取决于以下两种情况,取其最大的一种:- 加入
s[i]
所能组成的最长回文子序列长度,即:dp[i][j] = dp[i][j - 1]
。 - 加入
s[j]
所能组成的最长回文子序列长度,即:dp[i][j] = dp[i - 1][j]
。
下一步确定遍历方向。
- 加入
由于 dp[i][j]
依赖于 dp[i + 1][j - 1]
、dp[i + 1][j]
、dp[i][j - 1]
,所以我们应该按照从下到上、从左到右的顺序进行遍历。
最后输出 [0, size - 1]
范围内最长回文子序列长度,即 dp[0][size - 1]
为最终答案。
代码 #
|
|