1)???題目

Palindrome

Time Limit:?3000MS	?	Memory Limit:?65536K
Total Submissions:?46005	?	Accepted:?15688

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

2)????題意

題目給出回文的定義：一串字符，從左往右讀和從右往左讀是完全一樣的。比如aba，從左往右讀和從右往左讀都是aba。

給出一串字符，求使該字符串是回文需要添加的最少字符個數。

3)????數據范圍

字符串的長度n，3<=n<=5000。

4)????算法

動態規劃法。設字符串為S，長度為L，d[i][j]表示以第i個字符為首，第j個字符為尾的字符串構成回文最少需要添加的字符個數，i和j的初值分別為1、L。

如果S[i] == S[j]，即字符串兩端的字符相等，d[i][j] = d[i+1][j-1]，

即d[i][j]等于去掉頭尾后的字符串的d值。

如果S[i] != S[j]，此時劃分出兩個子問題，求d[i][j-1]和d[i+1][j]，它兩中較小的值再加1即為d[i][j]（加上的1個字符是用于和S[i]或者S[j]構成對稱的）。

狀態轉移方程：

從上面的分析可以看出，這個問題的實質是求最長公共子序列，只是這兩個序列分別是串S的前一部分和串S后一部分的逆序列。

5)????代碼

[cpp]?view plaincopyprint?

#include?<iostream>??

#include?<cstdio>??

#include?<cstring>??

??

using?namespace?std;??

??

#define?MIN(a,?b)?((a)?<?(b)???(a)?:?(b))??

??

#define?MAXSIZE?5005??

??

//開始沒有考慮內存問題，使用了int型，超內存限制，也可使用滾動數組解決??

unsigned?short?d[MAXSIZE][MAXSIZE];??

??

int?ToPalindrome(char?*s,?int?n)??

{??

????int?i,?j,?k;??

????//只有一個字符時，不需要添加字符??

????for?(i?=?0;?i?<?n;?i++)??

????{??

????????d[i][i]?=?0;??

????}??

????//串長度為2時??

????for?(i?=?1;?i?<?n;?i++)??

????{??

????????if?(s[i-1]?==?s[i])??

????????{??

????????????d[i-1][i]?=?0;??

????????}??

????????else??

????????{??

????????????d[i-1][i]?=?1;??

????????}??

????}??

??

????//串長度遞增??

????for?(k?=?2;?k?<?n;?k++)??

????{??

????????for?(i?=?0,?j?=?k;?j?<?n;?i++,?j++)??

????????{??

????????????if?(s[i]?==?s[j])??

????????????{??

????????????????d[i][j]?=?d[i+1][j-1];??

????????????}??

????????????else??

????????????{??

????????????????d[i][j]?=?MIN(d[i][j-1],?d[i+1][j])?+?1;??

????????????}??

????????}??

????}??

????return?d[0][n-1];??

}??

??

int?main(void)??

{??

????char?str[MAXSIZE];??

??

????int?n;??

????while?(scanf("%d",?&n)?!=?EOF)??

????{??

????????getchar();??

????????gets(str);??

????????printf("%d\n",?ToPalindrome(str,?n));??

????}??

????return?0;??

}??

6)????測試數據

5

Ab3bd

3

aaa

7

Aabcdba

7)????提交結果

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的动态规划——Poj 1159 Palindrome的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。