什么是回文
回文是指正向和反向拼写相同的单词、词组、数字或其他字符序列。例如，"racecar"就是一个回文。
问题背景
给定一个字符串，通过插入最少的字符使它变成一个回文序列。例如，对于字符串"AACECAAAA"，所需的最小插入次数为2，结果为"AAACECAAAA"。
动态规划求解
定义状态
我们可以定义一个二维数组dp来表示从i到j的最少插入次数，其中i和j分别表示字符串的起始位置和结束位置。
状态转移方程
如果s[i] == s[j]，那么dp[i][j] = dp[i + 1][j - 1]。
如果s[i] != s[j]，那么dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。
边界条件
对于单个字符，它本身就是一个回文序列，因此dp[i][i] = 0。
代码实现
下面是使用动态规划求解的代码实现：
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[0][n - 1];
}
按照题目要求进行修改
按照题目要求，最小插入次数不应该返回，而是应该返回插入后的回文字符串。在动态规划中加入一个二维数组path，用于记录每个状态的路径。
代码实现
下面是修改后的代码实现：
string minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
vector<vector<string>> path(n, vector<string>(n, ""));
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
path[i][j] = s[i] + path[i + 1][j - 1] + s[j];
} else {
if (dp[i + 1][j] < dp[i][j - 1]) {
dp[i][j] = dp[i + 1][j] + 1;
path[i][j] = s[i] + path[i + 1][j] + s[i];
} else {
dp[i][j] = dp[i][j - 1] + 1;
path[i][j] = s[j] + path[i][j - 1] + s[j];
}
}
}
}
return path[0][n - 1];
}
总结
这篇文章介绍了使用动态规划算法求解最小插入次数的方法，同时还对题目要求进行了修改，返回了插入后的回文字符串。使用动态规划算法可以在O(n^2)的时间复杂度内解决该问题。