题目描述
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。
比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。
注：此问题区分大小写
思路
解法一：奇思妙想
首先，我们要摸清回文串的特性，回文就是正着读反着读一样，一种非常对称不会逼死强迫症的字符串；这就是我们的突破口。。。你难道以为是逼死强迫症么？哈哈，太天真了，突破口其实是因为回文正着读反着读都相同的特性。。。这样我们就可以再建一个字符数组存储倒序的字符串
我们先分析下样例：ab3bd，
它的倒序是:db3ba
这样我们就可以把问题转化成了求最长公共自序列的问题，为啥可以这么转化呢？
它可以这么理解，正序与倒序“公共”的部分就是我们回文的部分，如果把正序与倒序公共的部分减去你就会惊奇的发现剩余的字符就是你所要添加的字符，也就是所求的正解
ad da把不回文的加起来就是我们梦寐以求的东西：回文串（卧槽？太没追求了）
把ad，da加起来成回文串就是adb3bda，所以这个问题就可以转化成了求最长公共自序列的问题，将字符串的长度减去它本身的“回文的”（最长公共自序列）字符便是正解
找到解题思路后我们就可以开始写了，最长公共自序列问题是个经典的dp问题，
最容易想到的方法就是开个二维数组dp【i】【j】，i，j分别代表两种状态；那么我们的动态转移方程应该就是
if (s[i] == s_[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
完整代码
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 5005
#define inf 1e9
#define ll long long
#define p pair<ll, ll>
char s[MAX], s_[MAX], t;
ll cnt = 0, dp[MAX][MAX];
int main() {
cin >> cnt >> s;
for (ll i = 0; i < cnt; i++) s_[cnt - i - 1] = s[i];
memset(dp, 0, sizeof(dp));
for (ll i = 1; i <= cnt; i++) {
for (ll j = 1; j <= cnt; j++) {
ll x = i - 1, y = j - 1;
if (s[x] == s_[y]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << cnt - dp[cnt][cnt] << endl;
}
但是并没有结束，由于数据量的问题，我们开了5000*5000的数组，MLE了，所以再使用滚动数组优化一下下。如果你仔细研究一下就会发现每次搜索到s的第i个元素的时候，数组dp【】【】真正使用到的元素仅仅是dp【i】【j】和dp【i-1】【k】（0 <= k <= n(n = strlen(s)）
即dp【】【】的第一下标从0–>i-2就没有用处了，因此我们可以开辟两个滚动数组来降低空间复杂度，状态转移公式变为
if (s[x] == s_[y]) dp[i % 2][j] = dp[(i % 2) ^ 1][j - 1] + 1;
else dp[i % 2][j] = max(dp[(i % 2) ^ 1][j], dp[i % 2][j - 1]);
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 5005
#define inf 1e9
#define ll long long
#define p pair<ll, ll>
char s[MAX], s_[MAX], t;
ll cnt = 0, dp[2][MAX];
int main() {
cin >> cnt >> s;
for (ll i = 0; i < cnt; i++) s_[cnt - i - 1] = s[i];
memset(dp, 0, sizeof(dp));
for (ll i = 1; i <= cnt; i++) {
for (ll j = 1; j <= cnt; j++) {
ll x = i - 1, y = j - 1, l = (i % 2) ^ 1;
if (s[x] == s_[y]) dp[i % 2][j] = dp[(i % 2) ^ 1][j - 1] + 1;
else dp[i % 2][j] = max(dp[(i % 2) ^ 1][j], dp[i % 2][j - 1]);
}
}
cout << cnt - dp[cnt % 2][cnt] << endl;
}
解法二：专属DP
需要稍作解释，
的时候，显然对着一对字符而言，我们不需要添加任何额外的字符，因此需要的字符数是子字符串需要的字符数。不相等的时候，我们有两种选择，在
位置的右边加上一个字符，或者在
位置的左边加上一个字符，选比较小的那个。
转载：https://blog.csdn.net/csyifanZhang/article/details/104852317