Palindrome
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 48269 Accepted: 16570
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
Ab3bdSample Output
2Source
IOI 2000
題意：
給一串字符，問最少加多少個字符可以使它變成回文字符串。
（回文字符串=從左往右看 和 從右往左看 串相同）
分析：
假設dp[i][j]表示字符串a[i..j]變成palindrome
至少需要花dp[i][j]個操作(i<=j)
那麼
如果a[i]=a[j]，那麼dp[i][j]=dp[i+1][j-1]
否則，就是dp[i][j] = min(dp[i-1][j], dp[i][j-1]) +1 這是因為要在前面或者後面補一個數
初始化為dp[i][i] = 0, dp[i][i+1]= a[i]==a[i+1] ? 0: 1
兩種寫法：
遞歸：
int getdp(int i,int j){
if(i == j) return 0;
if(i == j - 1) return a[i]==a[i+1] ? 0 : 2
if(dp[i][j] != -1) return dp[i][j]
if(a[i]==a[j]) return dp[i][j]=getdp(i + 1,j-1)
else return dp[i][j]=min(getdp(i, j-1),getdp(i+1, j))+1
}
遞推(i為間隔，間隔小的開始遞歸)
for(int i = 1;i<= n;i++){
for(int j = 0;j < n - i;j++){
if(a[j]==a[i+j]) dp[j][i+j] =dp[j+1][i+j-1]
else dp[j][i+j]=min(dp[j+1][i+j],dp[j][i+j-1])+1
}
}
注意dp[i][j]的范圍i<=j
感想：
1、如果這個題換一種思路還可以用
假設串s和它的逆串s'的最長公共子序列長度為L.
則需要添加的字符個數為 串長s-L。
2、除了用short避免MLE,還可以用dp中常出現的滾動數組或者動態滾動數組
來節省內存。
3、不過遞歸容易爆棧，斟酌著用。
4、終於搞清楚為什麼有時候寫的程序用c++提交AC，而用g++提交就wa。
要從計算機原理說起：
內存實際上連續的一片，申請內存的時候，一些語言會強制檢查越界，
比如java。c++這個實際上數據就是一個指針，比如dp[0]就是*dp，
dp[1]就是*(dp+1)。如果dp-1這塊內存恰好沒被使用，那麼dp[-1]就不會
報錯了。
如果一個二級數組dp的定義是dp[2][4]的話，那麼
dp[1][-1]實際上就是dp[0][3]，一些編譯器會報錯，一些不會。
在內存中，二級數據是這麼存的：
dp[0][0],dp[0][1],……,dp[0][M-1],dp[1][0],dp[1][1],……
在編譯器中，實際上會數組訪問這麼定位
dp[i][j] = *(dp+i*M+j)
5、最有趣的是我開始把dp的初始條件弄錯了，弄成
dp[i][i+1]= (a[i]==a[i+1]?0:2)了,結果用遞推寫AC了，用遞歸
卻是wa.要不是因為遞歸wa了，我還不會發現我這裡錯了。。
因為要加入的字符最少，所以盡管
ab可以加兩個字符使之變成abba、bab和aba.但是應該至少是加一個字符。
遞推AC代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
short dp[5005][5005];
char a[5010];
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
getchar();
gets(a);
for(i=0;i<n;i++)
{
dp[i][i]=0;
dp[i][i+1]=(a[i]==a[i+1]?0:1);
}
for(i=1;i<=n;i++)
{
for(j=0;j<n-i;j++)
{
if(a[j]==a[j+i])
dp[j][j+i]=dp[j+1][j+i-1];
else
dp[j][j+i]=min(dp[j][j+i-1],dp[j+1][j+i])+1;
}
}
printf("%d\n",dp[0][n-1]);
}
return 0;
}
//AC
//1407MS
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char a[5005];
short dp[5005][5005];
short getdp(int i,int j)
{
if(i==j) return 0;
if(i+1==j) return a[i]==a[j]?0:1;
if(dp[i][j]!=-1) return dp[i][j];
if(a[i]==a[j]) return dp[i][j]=getdp(i+1,j-1);
else return dp[i][j]=min(getdp(i,j-1),getdp(i+1,j))+1;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
getchar();
gets(a);
memset(dp,-1,sizeof(dp));
printf("%d\n",getdp(0,n-1));
}
return 0;
}
//AC
//1438MS
