湖大CG满分教程：作业训练四编程题20. 回文串（暴力×动态规划算法√）
问题描述
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。给你一个字符串，问最少在字符串尾添加多少字符，可以使得字符串变为回文串。
输入格式
有多组测试数据。
每组测试数据第一行是一个正整数N，表示字符串长度，接下来一行是长度为N的字符串，字符串中只有小写字母。
N=0表示输入结束，并且不需要处理。
40%的数列元素个数N 1 ≤ N≤ 100；
30%的数列元素个数N 1 ≤ N≤ 1000；
20%的数列元素个数N 1 ≤ N≤ 10000；
10%的数列元素个数N 1 ≤ N≤ 100000；
输出格式
对于每组测试数据，输出一个非负整数：添加最少的字符数，可以使得字符串变为回文串。
样例输入
3 aba 4 aaac 0
样例输出
0 3
【算法思想】
-
动态规划数组初始化：创建了一个二维数组
dp，大小为n x n，其中dp[i][j]表示子串s[i..j]是否是回文串的长度。 -
对角线初始化：将对角线上的元素
dp[i][i]初始化为 1，表示单个字符本身就是回文串。 -
动态规划计算：使用两个嵌套的循环，从字符串末尾开始，遍历所有子串。在这个过程中，你检查字符是否相等，然后根据不同情况更新
dp[i][j]的值。具体来说：- 如果
s[i] == s[j]，有以下两种情况：- 当
j - i <= 1时，表示当前子串的长度为 2 或者 1，因此直接将dp[i][j]设置为j - i + 1。 - 当
j - i > 1时，你检查dp[i + 1][j - 1]是否表示的子串是回文串，如果是，则更新dp[i][j]为dp[i + 1][j - 1] + 2，表示当前子串的长度为内部回文子串的长度加上 2。
- 当
- 如果
-
状态转移方程的核心思想是：通过计算已知较短子串的回文信息，来推导出更长子串的回文信息。的状态转移方程基于如下考虑：
当s[i] == s[j]时，如果j - i <= 1，则当前子串长度为 2 或 1，因此是回文串，直接将dp[i][j]设置为j - i + 1。当s[i] == s[j]且j - i > 1时，首先检查dp[i + 1][j - 1]是否表示的子串是回文串。如果是，说明当前子串也是回文串，因此更新dp[i][j]为dp[i + 1][j - 1] + 2，表示当前子串的长度为内部回文子串的长度加上 2。
if (s[i] == s[j]) {if (j - i <= 1) {dp[i][j] = j - i + 1;} else if (dp[i + 1][j - 1]) {dp[i][j] = dp[i + 1][j - 1] + 2;}
}
这个方程的含义是，如果当前子串的两端字符相等，那么要判断该子串是否为回文串，首先考虑 j - i <= 1 的情况，如果成立，说明子串长度为 2 或 1，是回文串，直接标记长度；否则，考虑 dp[i + 1][j - 1] 是否为回文串，如果是，那么当前子串也是回文串，长度为内部回文子串的长度加上 2。
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;int main()
{int n;while(cin >> n && n != 0) // 循环读取测试数据，直到 n 为 0 结束{string s;cin >> s; // 读取输入的字符串string x = s; // 创建一个与输入字符串相同的副本 xreverse(x.begin(), x.end()); // 将副本 x 反转if (x == s) // 如果副本 x 和原始字符串 s 相同，说明已经是回文串{cout << "0" << endl; // 输出结果为 0，无需添加字符}else{vector<vector<int>> dp(n, vector<int>(n, 0)); // 创建一个二维数组 dp，用于动态规划for (int i = 0; i < n; i++){dp[i][i] = 1; // 对角线上的元素置为 1，表示单个字符本身是回文串}int max = 0; // 用于记录最大的回文子串长度for (int i = s.size() - 1; i >= 0; i--) // 从字符串末尾开始向前遍历{for (int j = i; j < s.size(); j++) // 在 i 到字符串末尾范围内遍历{if (s[i] == s[j]) // 如果字符相同{if (j - i <= 1){dp[i][j] = j - i + 1; // 当 j - i <= 1 时，长度为 2 或者 1，直接标记回文串长度}else if (dp[i + 1][j - 1]) // 当 j - i > 1 时，查看内部子串是否是回文串{dp[i][j] = dp[i + 1][j - 1] + 2; // 更新回文串长度}}}}// 遍历最后一行，找到最大的回文子串长度for (int i = n - 1; i >= 0; i--){if (dp[i][n - 1] > max){max = dp[i][n - 1];}}cout << n - max; // 输出最少需要添加的字符数，即字符串长度减去最大回文子串长度}}return 0;
}