LeetCode：516.最长回文子序列 • The Sejolyn Memo

题目：516. 最长回文子序列 ↗

1 核心逻辑#

回文序列的定义是正读反读都一样。对于一个子串 $s[i \dots j]$ ，我们要找它的最长回文子序列，关键看它的两个端点字符 $s[i]$ 和 $s[j]$ ：

情况 A： $s[i] == s[j]$ ，如果首尾字符相等，那么这两个字符一定可以作为回文序列的最外层。

转移：我们只需要知道中间部分 $s[i+1 \dots j-1]$ 的最长回文长度，然后加上这两个字符。
方程： $dp[i][j] = dp[i+1][j-1] + 2$

情况 B： $s[i] \ne s[j]$ ，如果首尾不相等，说明它们两个不可能同时出现在同一个回文子序列的最外层。

转移：我们要么放弃 $s[i]$ ，看 $s[i+1 \dots j]$ 的结果；要么放弃 $s[j]$ ，看 $s[i \dots j-1]$ 的结果。
方程： $dp[i][j] = \max(dp[i+1][j], dp[i][j-1])$

2 状态定义与边界#

$dp[i][j]$ 表示字符串 $s$ 从下标 $i$ 到下标 $j$ 范围内的最长回文子序列的长度。

基础边界：

当 $i == j$ 时，单个字符本身就是回文，长度为 $1$ 。即 $dp[i][i] = 1$ 。
当 $i > j$ 时，区间不存在，长度为 $0$ 。

3 遍历顺序#

遍历顺序：观察状态转移方程，可以看到 $dp[i][j]$ 依赖于

左下方： $dp[i + 1][j - 1]$
下方： $dp[i + 1][j]$
左方： $dp[i][j + 1]$

因此遍历顺序：

$i$ 从大到小（从 $n - 1$ 倒退到 $0$ ）
$j$ 从小到大（从 $i + 1$ 前进到 $n - 1$ ）

4 代码实现#

public int longestPalindromeSubseq(String s) {
	char[] str = s.toCharArray();
	int n = str.length;
	int[][] dp = new int[n][n];
	
	// 初始化：单个字符都是回文串
	for (int i = 0; i < n; ++i) {
		dp[i][i] = 1;
	}
	
	// 从下往上遍历i
	for (int i = n - 1; i >= 0; --i) {
		// 从左往右遍历j
		for (int j = i + 1; j < n; ++j) {
			if (str[i] == str[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][n - 1];
}

java

5 空间优化#

可以看到， $dp[i][j]$ 只依赖于「本行左侧」和「下一行」的值，因此二维矩阵可以压缩成一维数组。

public int longestPalindromeSubseq(String s) {
	char[] str = s.toCharArray();
	int n = str.length;
	int[] dp = new int[n];
	Arrays.fill(dp, 1);

	for (int i = n - 1; i >= 0; --i) {
		int pre = 0; // 相当于dp[i + 1][j - 1]
		for (int j = i + 1; j < n; ++j) {
			int tmp = dp[j];
			if (str[i] == str[j]) {
				dp[j] = pre + 2;
			} else {
				dp[j] = Math.max(dp[j - 1], dp[j]);
			}
			pre = tmp;
		}
	}

	return dp[n - 1];
}

java