[算尽天下系列第7期]LeetCode·516·最长回文子序列

LeetCode 516 最长回文子序列

题目描述

给定一个字符串 s，找到其中最长的回文子序列。可以假设 s 的最大长度为 1000。

样例

样例输入1

bbbab

样例输出1

4

样例解释1

一个可能的最长回文子序列为 bbbb。

样例输入2

cbbd

样例输出2

2

样例解释2

一个可能的最长回文子序列为 bb。

算法与数据结构

动态规划

题解

再多看几道动态规划的题目，长老就要和大家分享微软、字节跳动等大公司笔试中的动态规划真题啦，所以大家一定要认真消化这几题哦。

最长回文子序列也是动态规划中的经典题目，这次不再是线性规划了，而是二维矩阵，不过理解起来也很容易。

回顾线性规划中，我们往往定义 dp[i] 为到 i 为止符合题目要求的解的值，而在二维动态规划中，我们往往定义 dp[i][j] 表示从 i 到 j 这一段中符合题目要求的解的值。

例如对于这道题，我们定义 dp[i][j] 表示字符串从 i 到 j 的子串中，最长子序列的长度。最终，dp[0][n - 1] 就是答案。

那么，状态转移呢？

为了得到 dp[i][j]，我们可以考察 s[i] 和 s[j]，如果这两个位置上的字符是一样的，那么显然，dp[i][j] = dp[i + 1][j - 1] + 2。

如果这两个位置上的字符是不一样，那么，取 dp[i + 1][j] 和 dp[i][j - 1] 中较大的即可。

最后考虑初始条件，初始条件就是当长度为 1 时，自然成为回文序列，于是，dp[i][i] = 1 对任意的 i 成立。

但是在写代码的时候，我们需要注意，这里数组下标的循环并不能简单从 1 循环到 n：

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
		// TODO
	}
}

通过简单比对样例输入输出可以很容易发现，状态转移并不是随着下标推进的，而是随着下标之间的距离（即 i 和 j 之间的距离）推进的：我们首先得到了 dp[i][i] 的值，都等于 1，也就是所有长度为 1 的子串，我们得到了它的最长回文子序列的长度，下面应该去计算所有长度为 2 的子串，再长度为 3 的子串……只有这样，我们比较 s[i] 和 s[j] 才是有意义的。

所以，一种常见的技巧就是以跨度 len 为外层循环，以下标 i 为内层循环，在循环内计算下标 j。

for (int len = 1; len <= length; len++) {
	for (int i = 0; i + len - 1 < length; i++) {
		int j = i + len - 1;
		// TODO
	}
}

完整代码

int length = s.length();
int[][] dp = new int[length][length];
for (int len = 1; len <= length; len++) {
    for (int i = 0; i + len - 1 < length; i++) {
        int j = i + len - 1;
        if (i == j) {
            dp[i][j] = 1;
        } else {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
}
return dp[0][length - 1];