题目描述

直接暴力的通过是很简单的，但我最近学习了最长回文子序列的判定方法，如何用 DP 把简单问题复杂化，是我们今天要考虑的（虽然没有半点实用性）。

最长回文子序列样例

for (int i = 1; i <= n; i ++)
    for (int j = n; j >= 1; j --)
        if (s[i] == s[j]) dp[i][j] = max(dp[i - 1][j + 1] + 1, dp[i][j]);
        else dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]);
// 状态转移方法，考虑逆序字符串和字符串的公共子序列

发现，最长回文子序列和最长回文子串有两点区别
1. 最长回文子串在两个字符不相等的情况下，不会继承旁边少考虑一个字符的最大长度，而是直接清零
2. 最长回文子序列不需要两个序列相邻，也就是说，有可能 一个字符串“54321....12345”可以被判定为回文子序列，因为中间的字符对于子序列来说都是要删除的部分，因此要对逆序的字符串和正序的字符串指针所在位置进行判定，以确保两个考虑好了的字符串是同一个，而不是中间相隔了很多字符的不同两个字符串

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(DP) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string a;
    getline(cin, a);
    int n = a.size();
    vector<vector<int>> dp(n + 2, vector<int> (n + 2));
    a = ' ' + a;

    int ans = 0;
    for (int i = 1; i <= n; i ++)   
        for (int j = n; j >= 1; j --)
        {
            // 这里有问题，有可能回文的部分不连接，比如12345....54321
            if (a[i] == a[j]) dp[i][j] = dp[i - 1][j + 1] + 1;
            else dp[i][j] = 0;
            if (j <= i && dp[i][j] >= i - j) ans = max(ans, dp[i][j]);
        }

    cout << ans << endl;

    return 0;
}