求最少補多少個字符使所給字符串變成回文，直接dp，dp[i][j]代表從i到j的字串中最少補的字符。1、如果a[i]==a[j]，dp[i][j]=dp[i+1][j-1]，不用加新字符的情況；2、如果a[i]!=a[j]，dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1，在中間字符串的基礎上再補一個字符；n的范圍是5000二維會超內存，這裡注意每次dp[i][j]的更新都用到dp[i+1]和dp[i][j-1],j-1可以讓j為升序，dp[i+1]用滾動數組存，因為每次只用到兩層dp（和下標的奇偶性），讓i降序，即可使每次計算dp[i][j]時，dp[i+1]和dp[i][j-1]均為已知，dp[2][5000]實現dp過程。 Palindrome Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2084 Accepted Submission(s): 725 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 [cpp] #include<stdio.h> #include<string.h> #define size 5010 int n,dp[2][size]; char a[size]; int min(int a,int b) { return a>b?b:a; } int main() { int i,j,k,l,m; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); getchar(); scanf("%s",&a); for(i=n-2;i>=0;i--) { for(j=i+1;j<n;j++) { if(a[i]==a[j]) dp[i%2][j]=dp[(i+1)%2][j-1]; else dp[i%2][j]=min(dp[(i+1)%2][j],dp[i%2][j-1])+1; } } printf("%d\n",dp[0][n-1]); } return 0; } 貼一個網上的例子 滾動數組很適合用在二維ＤＰ而且是數組在很大時，可以節省內存，消除超內存的隱患！具體思想還是看了網上的資料，轉載一個，共同享用吧！ 滾動數組 舉個簡單的例子： int i,d[100]; d[0]=1;d[1]=1; for(i=2;i<100;i++) d[i]=d[i-1]+d[i-2]; printf("%d",d[99]); 上面這個循環d[i]只需要解集中的前2個解d[i-1]和d[i-2]; 為了節約空間用滾動數組的方法 int d[3]; d[0]=1;d[1]=1; for(i=2;i<100;i++) d[i%3]=d[(i-1)%3]+d[(i-2)%3]; printf("%d",d[99%3]); 注意上面的運算，我們只留了最近的3個解，數組好象在“滾動?一樣，所以叫滾動數組 對於二維數組也可以用這種方法 例如： int i,j,d[100][100]; for(i=1;i<100;i++) for(j=0;j<100;j++) d[i][j]=d[i-1][j]+d[i][j-1]; 上?的d[i][j]忪便賴於d[i-1][j],d[i][j-1]; 迿用滾動數組 int i,,j,d[2][100]; for(i=1;i<100;i++) for(j=0;j<100;j++) d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1]; 滾動數組實際是一種節約空間的辦法，時間上沒什麼優勢，多用於DP中，舉個例子先： 一個DP，平常如果需要1000×1000的空間，其實根據DP的特點，能以2×1000的空間解決問題，並且通過滾動，獲得和1000×1000一樣的效果。
