题解：洛谷 P1435 [IOI 2000] 回文字串

【题目来源】

洛谷：P1435 [IOI 2000] 回文字串 - 洛谷

【题目描述】

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 \(Ab3bd\) 插入 \(2\) 个字符后可以变成回文词 \(dAb3bAd\) 或 \(Adb3bdA\)，但是插入少于 \(2\) 个的字符无法变成回文词。

注意：此问题区分大小写。

【输入】

输入共一行，一个字符串。

【输出】

有且只有一个整数，即最少插入字符数。

【输入样例】

Ab3bd

【输出样例】

2

【解题思路】

【代码详解】

《洛谷 P1435 回文子串》 #动态规划,dp# #IOI# #2000#

#include <bits/stdc++.h>
using namespace std;const int N = 1005;  // 定义最大字符串长度string s1, s2;        // s1: 原始字符串，s2: 反转后的字符串
int dp[N][N];         // DP数组，用于存储最长公共子序列长度int main()
{// 输入原始字符串cin >> s2;// 复制原始字符串并反转string s1 = s2;reverse(s2.begin(), s2.end());// 在字符串前添加空格，使索引从1开始s1 = " " + s1;s2 = " " + s2;int len = s1.size();  // 获取字符串长度（包含前导空格）// 动态规划计算最长公共子序列for (int i = 1; i <= len; i++){for (int j = 1; j <= len; j++){if (s1[i] == s2[j]){// 字符匹配，长度加1dp[i][j] = dp[i - 1][j - 1] + 1;}else{// 字符不匹配，取上方或左方的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 输出需要插入的最少字符数（总长度减去最长回文子序列长度）cout << len - dp[len][len];return 0;
}

【运行结果】

Ab3db
2