自动搬运

查看原文

来自洛谷，原作者为

	AFO_Lzx Inter Milano is the greatest football club in the world! || 终于有钩子了 || AFOed

搬运于2025-08-24 21:18:43，当前版本为作者最后更新于2025-06-14 13:00:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

退役后的第一篇题解，OI，永别了。

很显然应该用 $O(n^2)$ 的做法，区间 DP 应该是个不错的选择。

• 设计状态：设 $f_{i,j}$ 为从 $i$ 到 $j$ 中最长回文子序列的长度。

• 确定答案：很显然，因为字符串的下标从 $0$ 开始，所以答案为 $f_{0,n-1}$，也就是从 $0$ 到 $n-1$ 中最长回文子序列的长度。

• 状态转移：

  ① 当 $s_i=s_j$ 时，可以构成一个回文子序列，$f_{i,j}=f_{i+1,j-1}+2$。

  ② 当 $s_i\ne s_j$ 时，不能构成，$f_{i,j}=\max(f_{i+1,j},f_{i,j-1})$。

• 初始化：很显然，长度为 $1$ 的区间的最长回文子序列的长度为 $1$，故 $f_{i,i}=1$。

可以通过本题的代码如下：

#include<bits/stdc++.h>
using ll = long long;
using namespace std;

const int N = 1e3 + 5;
int n, f[N][N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	string s;
	cin >> s;
	
	for (int i = 0; i < n; i++) {
		f[i][i] = 1;
	}
	for (int l = 2; l <= n; l++) {
		for (int i = 0; i < n - l + 1; i++) {
			int j = i + l - 1;
			if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
			else f[i][j] = max(f[i][j - 1], f[i + 1][j]);
		}
	}
	cout << f[0][n - 1] << '\n';
	return 0;
}