洛谷 P1435 回文字串题解

y0k1n0

2025 年 03 月 06 日

6 次浏览

暂无评论

1038字数

动态规划思维

# 洛谷 P1435 回文字串 题解

## 题目描述

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

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

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

## 输入

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

## 输出

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

## 解题思路

这道题需要思考回文串的性质， 顾名思义， 回文串是一个正着读和反着读都相同的字符串， 因此可以从这里出发去寻找解题思路

```
Ab3bd
db3bA
```

为了让字符串正着读和反着读都相同， 最简单的方式是让正着读的字符串的子序列中包含反着读的字符串

A<font color=#0099ff>db3b</font>d<font color=#0099ff>A</font>

其中蓝色表明的字段即为反着读的字符串， 因此最小的添加长度为字符串的长度减去正着读和反着读的字符串的最长公共子序列

证明如下(不靠谱， 是我解题时候的思路)：

- 假设存在一个更小的解法，得到的回文串的子序列中不包含原字符串的逆序， 则在原字符串的逆序中一定存在一个字符`c`没有插入输入串且这个字符在原字符串中没有对应的位置， 则意味着原字符串中`c`对应的位置不满足回文串的条件

## AC代码

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;

string s1, s2;
int n;
int dp[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> s1;
    n = s1.length();
    s1 = ' ' + s1;
    s2 = s1;
    reverse(s2.begin() + 1, s2.end());
    // cout << s1 << s2 << endl;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if(s1[i] == s2[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    cout << n - dp[n][n] << endl;
	return 0;
}
```

最后修改：2025 年 03 月 07 日