简单分析, 本题属于$2D/0D$问题,所以空间复杂度为$n^2$, 时间复杂度也是$n^2$

这里我们定义$dp$方程$dp[i][j]$为i到j的子字符串变为回文字符串需要插入的字符的个数

初始化$dp[i][j]$为$inf$, $dp[i][i] = 0$ 显然$dp[i]j[j]$可以从$dp[i + 1][j - 1]$转移过来, 也可以从$dp[i + 1][j]$或者$dp[i][j - 1]$转移过来, 我们只取三者最小值即可.

$ dp[i][j] = \begin{cases} min\{dp[i + 1][j - 1]\}& \text{if s[i] = s[j]}\\ min\{dp[i + 1][j] + 1, dp[i][j - 1] + 1\}& \text{if s[i]$\ne$s[j]}\\ 0 & \text{if i=j or (s[i]=s[j] and i+1=j)}\\ \end{cases}\\ $

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <vector>
 5 #include <cstring>
 6 #include <algorithm>
 7 using namespace std;
 8 constexpr int MAXN = 1e3 + 7;
 9 
10 using ll = long long;
11 
12 int dp[MAXN][MAXN];
13 
14 int main()
15 {
16     ios::sync_with_stdio(false);
17     cin.tie(nullptr);
18     cout.tie(nullptr);
19     memset(dp, 0x3f, sizeof dp);
20     string s;
21     cin >> s;
22     int n = s.length();
23     s = " " + s;
24     for (int i = 1; i <= n; ++i)
25     {
26         dp[i][i] = 0;
27     }
28     for (int len = 1; len <= n - 1; ++len)
29     {
30         for (int i = 1; i <= n - len; ++i)
31         {
32             int j = i + len;
33             if (s[i] == s[j])
34             {
35                 dp[i][j] = min(dp[i][j], len == 1 ? dp[i][i] : dp[i + 1][j - 1]);
36             }
37             else
38             {
39                 dp[i][j] = min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);
40             }
41         }
42     }
43     cout << dp[1][n] << '\n';
44 
45     return 0;
46 }