dp问题添加最少的字符构成回文串

逃离我推掉我的手 2022-06-18 09:50 136阅读 0赞

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.  
  
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.  
Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

Sample Input

5
    Ab3bd

Sample Output

思路：将原串倒置得到现串，找到两个串的最长公共子串的长度，长度n-找到的公共长度就是需要添加的字符数

先贴如一个何求得两个穿的最长公共子串的代码

#include <iostream>
    #include <cstring>
    #include <string>
    using namespace std;
    string a,b;
    int dp[1000][1000];
    int main()
    {
    	int num,i,j,l1,l2,maxn;
    	while(cin>>a>>b)
    	{
    	  l1=a.size();
    	  l2=b.size();
    	  memset(dp,0,sizeof(dp));
    	  
    	  for(int i=0;i<l1;i++) 
    	  for(int j=0;j<l2;j++)
    	  {
    	  	if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
    	  	else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
    	  }
    	  cout<<dp[l1][l2]<<endl;
    	  
    	}
    	return 0;
    }

在这个问题中如果定义dp\[5005\]\[5005\]肯定会内存超限

所以用滚动数组解决,其实这个题中每次用到的dp行数是当前行和前一行 所以我们可以只用dp\[2\]\[5005\]就可以啦

代码如下：只是在上一个程序中改动一下即可

#include <stdio.h>  
    #include <string.h>   
    #include <iostream>  
    #include <algorithm>   
    using namespace std;  
    char str1[5010];  
    char str2[5010];  
    int dp[2][5010];     //滚动数组 解决内存超限问题 
    int main()  
    {  
        int n,i,j;  
        while(~scanf("%d",&n)){  
            getchar();  
            for(i=1;i<=n;i++)
    		{  
                scanf("%c",&str1[i]);  
                str2[n-i+1]=str1[i];  
            }  
            memset(dp,0,sizeof(dp));  
            for(i=1;i<=n;i++)  
            for(j=1;j<=n;j++){  
              if(str1[i]==str2[j])  
                    dp[i%2][j]=dp[(i-1)%2][j-1]+1;  
                else  
                    dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);  
            }  
            printf("%d\n",n-dp[n%2][n]);  
        }  
        return 0;  
    }