51nod 1092 回文字符串 dp问题

短命女 2022-08-20 12:23 18阅读 0赞

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。

例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。

分析：

该题目有两种不同的思路，想到了就非常简单。

解法一：

这种解法相对来说就是一般的dp思想，没有什么套路。

我们尝试将给出的字符串的所有子串都找到，怎么划分呢。可以按子串的起始位置和长度来划分。

dp\[i\]\[j\]表示的是从第i个字符开始长度为j的子串变为回文串需要添加的最少字母数，最终要求并的是dp\[0\]\[n\]

递推公式看代码，有了上面的思路递推公式就比较简单了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    int const maxn = 1005 ;
    int dp[maxn][maxn] ;
    //dp[i][j] 表示的是从第i个字符开始长度为j的子串变为回文串需要添加的最少字母数
    //最终要求的结果为dp[0][n]
    char str[maxn];
    
    int main()
    {
        while(scanf("%s",str)!=EOF)
        {
            int n = strlen(str);
            memset(dp,0,sizeof(dp));
            //初始化,明显长度为0以及长度为1的子串本身就为回文串，添加的字母数为0
            for(int i = 0 ; i < n ; i++)
            {
                dp[i][0] = dp[i][1] = 0 ;
            }
            for(int j = 2 ; j <= n ; j++)
            {
                for(int i = 0 ; i < n ; i++)
                {
                    //j为长度，i子串的起始位置
                    if(str[i]==str[i+j-1])
                    {
                        //子串的首尾字符相同，那么它的结果就和去掉首尾字符烦人子串一样
                        dp[i][j] = dp[i+1][j-2];
                    }
                    else dp[i][j] = min(dp[i][j-1],dp[i+1][j-1])+1 ;
                    //子串首尾字符不相同的话，那么就去掉首或者尾然后加上1
                }
            }
            printf("%d\n",dp[0][n]);
        }
        return 0 ;
    }

解法二：

第二种解法就是利用最长公共子序列来求解。

将给定的字符串反转之后，求出这两个字符串的最长公共子序列，然后用长度减去这个子序列就是我们要求的解。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    int const maxn = 1005 ;
    int dp[maxn][maxn] ;  //求最长公共子序列
    string str1,str2;
    
    int main()
    {
        while(cin>>str1)
        {
            int n = str1.size();
            str2 = str1 ;
            memset(dp,0,sizeof(dp));
            reverse(str2.begin(),str2.end());
            for(int i = 0 ; i < n ; i++)
            {
                for(int j = 0 ; j < n ; j++)
                {
                    if(str1[i]==str2[j]) dp[i+1][j+1]=dp[i][j]+1;
                    else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
                }
            }
            printf("%d\n",n-dp[n][n]);
        }
        return 0;
    }