算法 - 最长回文子序列（最长回文子串动态规划图解）

~ 题干 ~

首先什么是回文字：

回文字定义：简单解释就是镜像对撑的字符串，例如 “aba”、“abba” 都属于回文字，当然单个字符例如 “a” 也是回文字。

题目：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

例1：s = "bbbab"，返回4

解释：最长回文子序列为 “bbbb”，长度是4。

例2：s = "cbbd"，返回2

解释：最长回文子序列为 “bb”，长度是2。

限制条件：输入的字符串s只会包含小写英文字母

~ 算法理解 ~

思路：动态规划

通过动态规划的递归式（状态迁移表达式），逐步把问题简单化，直到简单到一眼就可以看出答案（递归边界条件）。

既然是递归的思路，我们应该考虑，如果当前状态已经知道了答案，那再更进一步的条件下能否知道答案。

举例：

如果知道字符串 s1 的最长回文子序列长度为 n1，能否推出 s1 + 某一个字符的最长回文子序列长度？

考虑如下几种情况：

1. 如果 s1 的首尾两个字符是相同的字符：

如上图，很显然，如果首尾两个字符是相同的，那去掉首尾2个字符的最长回文子序列长度为 n1 - 2。

2. 如果 s1 的首尾两个字符是不同的字符：

如上图，如果 s1 首尾两个字符不同，那 s1 的最长回文子序列长度 = max(最长回文子序列m1，最长回文子序列m2)

即：m1 和 m2 哪个大就取哪个。

用一个二维数组dp[i][j]表示从字符串 s 的第 i 位到第 j 位他的最长回文子序列的长度。

可以用如下表表示：（假设字符串 s 长度为10）

如果：i = j，dp[i][j] = 1，因为表示就一个字符，所以最长回文子串长度一定是1

如果：i > j，dp[i][j] = 0, 表示不存在子串，因为第二个下标比第一个下标小

表格变为如下：

如果：i < j，

情况1（i，j位置的2个字符一样）：dp[i][j] = dp[i+1][j-1] + 2

情况2（i，j位置的2个字符不一样）：dp[i][j] = max(dp[i][j-1], dp[i+1][j])

表格如下：

有了状态迁移方程，接下来逐个确定未知方块，根据条件不同，我们可以从 “右上角” 逐步往 “左下角” 推演。

最终最 “左下角” 的位置就是我们要找的答案！

~ 总结 ~

动态规划最关键的是能从题目中抽象出状态转移方程。

例如上题中的 dp[i][j]，整个 dp[i][j] 二维数组其实就是一个辅助道具，有点像我们在做几何题目中的辅助线。

有了好的 “辅助线”，才能够思路清晰的解题。