转换法
// 区间DP
// 转换:添加最少的字符 to 回文子串
// 相当于求出 最长回文子序列 t
// 然后补上 不在 t 中字符即可
#include <iostream>
#include <cstring>
using namespace std;
constexpr int N = 1010;
// 从 l 到 r 中最长回文子序列的长度 为 f[l][r]
int f[N][N];
string s;
int main()
{
cin >> s;
int n = s.size();
s = "*" + s;
for(int len = 1;len <= n; ++ len) { // 枚举长度
for(int l = 1;l + len - 1 <= n; ++ l) { // 枚举起点
int r = l + len - 1;
if(len == 1) f[l][r] = 1;
else {
// 选r,选l
f[l][r] = max(f[l + 1][r], f[l][r - 1]);
// 选两端
if(s[l] == s[r]) f[l][r] = max(f[l][r], f[l + 1][r - 1] + 2);
}
}
}
cout << n - f[1][n] << endl;
return 0;
}
直接求
思路来自:1070. 括号配对
f[i][j] 表示:
s[l, r] 变成回文串的最小操作数 为 f[i][j];
#include <iostream>
#include <cstring>
using namespace std;
constexpr int N = 1010;
// 将s[l, r] 变成回文串的最小操作数 为 f[i][j];
int f[N][N];
string s;
int main()
{
cin >> s;
int n = s.size();
s = "*" + s;
for(int len = 1;len <= n; ++ len) { // 枚举长度
for(int l = 1;l + len - 1 <= n; ++ l) { // 枚举起点
int r = l + len - 1;
if(len == 1) f[l][r] = 0; // 只有一个元素 ,已经回文
else {
// 由左边添加一个,或者右边添加一个, 需要操作一次
f[l][r] = min(f[l + 1][r], f[l][r - 1]) + 1;
// 直接扩展
if(s[l] == s[r]) f[l][r] = min(f[l][r], f[l + 1][r - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}