【2024.12.30练习】密码脱落

2025/9/27 0:25:37 来源：https://blog.csdn.net/FeAtherHZM/article/details/144828727 浏览: 次关键词：【2024.12.30练习】密码脱落

题目描述

题目分析

一、题目转换

通过添加字符形成的回文字符串问题可以通过以下方式解决：对于已有的字符串，可以先求出其内部的最大子序列回文字符串，然后计算剩余字符数量，即为要添加的字符数。

例如，ABDCDCBABC序列（长度为10）中，内部的最长回文字符串为

ABDCDCBABC或ABDCDCBABC（长度为7），

则可以扩充为CBABDCDCDBABC或CBABCDCDCBABC，

二者都是添加3个字符使原来未配对的3个字符配对。

二、思路求解

经过思考后，该问题可以转化为动态规划问题求解。设二维数组 $dp[i][j]$ 为字符串从第 $i$ 个字符到第 $j$ 个字符内部的最长回文字符串。则初始状态为：
$dp[i][i]=1$

$dp[i][i+1]=\begin{Bmatrix} 2,&str[i]=str[i+1]\\ 1,& str[i]\neq str[i+1] \end{Bmatrix}$

状态转移方程为：

$dp[i][j]=\begin{Bmatrix} max(dp[i][j-1],dp[i+1][j]) ,&str[i]\neq str[j] \\ max(dp[i][j-1],dp[i+1][j],dp[i+1][j-1]+2) ,& str[i]=str[j] \end{Bmatrix}$

需要注意的是，在DP过程中，设i为所求子串的长度，j为子串第一个字符在总字符串中的位置。通过i,j的双重循环即可遍历所有状态，时间复杂度为1e6，符合要求。

我的代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
string str;
int n;
int dp[1005][1005];
int main() {cin >> str;n = str.length();//DPfor (int i = 0; i < n; i++){dp[i][i] = 1;}for (int i = 0; i < n - 1; i++){if (str[i] == str[i + 1]) {dp[i][i + 1] = 2;}else {dp[i][i + 1] = 1;}}for (int i = 2; i < n; i++)//i为所求子串的长度{for (int j = 0; j < n - i; j++)//j为子串第一个字符在总字符串中的位置{if (str[j] != str[i + j]) {dp[j][i + j] = max(dp[j][i + j - 1], dp[j + 1][i + j]);}else {dp[j][i + j] = max(max(dp[j][i + j - 1], dp[j + 1][i + j]), dp[j + 1][i + j - 1] + 2);}}}cout << n - dp[0][n - 1];return 0;
}