算法

(区间DP) $O(n^2)$

设计状态：
用 f[i][j] 表示字符串 $s[i…j]$ 中至少要插入的字符数量。
思考转移：
如果 $s[i] == s[j]$，显然有 $f[i][j] = f[i + 1][j - 1]$
否则 $f[i][j] = \min(f[i][j - 1], f[i + 1][j]) + 1$

C++ 代码

#include <iostream>

using namespace std;

int n;
string s;
short f[5005][5005];

int main() {
    cin >> n >> s;

    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j < n; ++j) {
            if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1];
            else f[i][j] = min(f[i][j - 1], f[i + 1][j]) + 1;
        }
    }

    cout << f[0][n - 1] << '\n';

    return 0;
}