「动态规划」最长回文子序列

题目

最长回文子序列

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例1: 输入: “bbbab” 输出: 4 一个可能的最长回文子序列为 “bbbb”。 示例2: 输入: “cbbd” 输出: 2 一个可能的最长回文子序列为 “bb”。 提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

定义dp

对于dp(i,j)：

字串s[i…j]的最长子序列为dp(i,j)。

状态转移函数

# 如果s[i] == s[j],则s[i]和s[j]一定在最长回文子序列中
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))

base case

当 j == i 时，此时最长回文子序列为 s[i]。最长回文子序列长度为1。