Palindrome

poj1159

题目

Problem Description 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

2

题目大意：给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

解题思路

什么是回文串？

正读和反读都一样的字符串（原串与其逆串相同）

通过插入构成回文串，那么这道题可以等价于原串与逆串的最小编辑距离。

最小编辑距离：是用以衡量两个字符串之间的相似度，是两个字符串之间的最小操作数，即从一个字符转换成另一个字符所需要的操作数，包括插入、删除和置换。

这道题的最小编辑距离：插入字符串的长度。

pl: 最终回文串的长度 ol：初始串的长度 il：插入字符串的长度

lcs：初始串与其逆串的最长公共子序列的长度。

1）pl = ol + il

2）pl = lcs + 2*il。

3）回文串的最长公共子序列的长度等于回文串的长度。

综上，il = ol - lcs

代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn = 5000 + 5;
char a[maxn], b[maxn];
short dp[maxn][maxn];
int main()
{
    int n;
    while(cin >> n)
    {
        for(int i = 1; i <= n; i ++)
        {
            cin >> a[i];
        }
        int num = 0;
        for(int i = n; i >= 1; i --)
        {
            b[++num] = a[i];
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                if(a[i] == b[j])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        int ans = n-dp[n][n];
        cout << ans << endl;
    }
    return 0;
}