题目描述

原题地址：COGS

思路

本来没有什么想法，搜了一下题解之后发现一个很妙的方法，将字符串正反各读一遍，然后求最长公共子序列的长度，最后再用总长度减一下就可以了

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5100;
char s[maxn], rs[maxn];
int f[maxn][maxn];
int len;
int main()
{
    freopen("palin.in", "r", stdin);
    freopen("palin.out", "w", stdout);
    scanf("%d%s", &len, s + 1);
    for (int i = 1, j = len; i <= len; ++i, --j)
        rs[i] = s[j];
    for (int i = 1; i <= len; ++i)
        for (int j = 1; j <= len; ++j)
        {
            if (s[i] == rs[j])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    cout << len - f[len][len] << endl;
}