湖大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

【算法思想】

1. 动态规划数组初始化：创建了一个二维数组 dp，大小为 n x n，其中 dp[i][j] 表示子串 s[i..j] 是否是回文串的长度。

2. 对角线初始化：将对角线上的元素 dp[i][i] 初始化为 1，表示单个字符本身就是回文串。

3. 动态规划计算：使用两个嵌套的循环，从字符串末尾开始，遍历所有子串。在这个过程中，你检查字符是否相等，然后根据不同情况更新 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。

4. 状态转移方程的核心思想是：通过计算已知较短子串的回文信息，来推导出更长子串的回文信息。的状态转移方程基于如下考虑：

   当 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;
}