7-6 回文串问题（25 分)

╰+哭是因爲堅強的太久メ 2022-03-08 09:48 57阅读 0赞

### 题目描述： ###

一个字符串，如果从左到右读和从右到左读是完全一样的，比如"aba"，我们称其为回文串。现在给你一个字符串，可在任意位置添加字符，求最少添加几个字符，才能使其变成一个回文串。

输入格式:  
任意给定的一个字符串，其长度不超过1000.

输出格式:  
能变成回文串所需添加的最少字符数。

输入样例:  
在这里给出一组输入。例如：

Ab3bd  
Abb  
输出样例:  
在这里给出相应的输出。例如：

2  
1

###### 分析： ######

这个题其实如果读懂了方法其实挺简单的。  
就是一个将原字符串和逆序的字符串的最长公共子序列求出来。  
所求得的值就是已经匹配的字符串。  
然后用长度减去已经匹配的字符串长度，即为答案。  
所以，这里有一个求最长公共子序列的dp问题。  
参考dp博客： [https://blog.csdn.net/someone\_and\_anyone/article/details/81044153][https_blog.csdn.net_someone_and_anyone_article_details_81044153]  
参考博客：[https://blog.csdn.net/qq\_33435265/article/details/51242588][https_blog.csdn.net_qq_33435265_article_details_51242588]  
AC代码：

#include <stdio.h>
    #include"cstdio"
    #include"iostream"
    #include"string.h"
    #include"algorithm"
        using namespace std;
    char str[1001];
    int dp[1001][1001];
    int main()
    {
    
        memset(dp,0,sizeof(dp));
        char str1[1001];
        scanf("%s",str);
        int len=strlen(str);
        int j=len-1;
        for(int i=0;i<len;i++)
            str1[j--]=str[i];
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=len;j++)
                if(str[i-1]==str1[j-1])
                   dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
        printf("%d\n",len-dp[len][len]);
    }

##### 分析： #####

同时这其实就是一个求最长公共回文串的dp。  
参考博客：[https://www.cnblogs.com/AndyJee/p/4465696.html][https_www.cnblogs.com_AndyJee_p_4465696.html]

[https_blog.csdn.net_someone_and_anyone_article_details_81044153]: https://blog.csdn.net/someone_and_anyone/article/details/81044153
[https_blog.csdn.net_qq_33435265_article_details_51242588]: https://blog.csdn.net/qq_33435265/article/details/51242588
[https_www.cnblogs.com_AndyJee_p_4465696.html]: https://www.cnblogs.com/AndyJee/p/4465696.html