題意： 給你一串字符串，讓你求最少加入幾個字符，才能使得這個字符串是個回文串。 做法： 設a[i]是這個字符串,b[i]是這個字符串的逆序串。 那麼a[i],b[i]的最長公共子序列就是所求的字符串裡擁有的最大的回文串。 然後用總串長減去最大的回文串長度即為所求。 求最長公共子序列的公式為： dp[i][j]=max(dp[i-1] [j],dp[i][j-1]) if(a[i]==b[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); 如果直接求的話，勢必要開一個5001*5001的數組，鐵定MLE。 有一下兩種解決方法： 1，開short int型數組 這是poj返回的結果： 2，運用動態數組。 根據dp滾動的過程我們可以知道，dp【i】【j】的值不會與dp[i-2][0.....n]的值有關系。 那麼可以把dp[i][j]的值覆蓋到dp[i-2][j]上。即dp[i][j]為dp[i%2][j]； poj返回的結果： 對比以上兩種方法，顯而易見的可以得出2的方法很節約空間，就是耗時略長。 1，short int數組 [html] #include<iostream> #include<stdio.h> #include<string.h> #define max(a,b) (a>b?a:b) using namespace std; short int dp[5001][5001]; int main() { int a[5001]; int b[5001]; int i,j; int n; char str; cin>>n; getchar(); for(i=1;i<=n;i++) { scanf("%c",&str); a[i]=str; b[n-i+1]=str; } for(i=0;i<=n;i++) { dp[i][0]=0; dp[0][i]=0; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dp[i][j]=max(dp[i][j-1],dp[i-1][j]); if(a[i]==b[j]) { dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); } } } int len; len=dp[n][n]; printf("%d\n",n-len); return 0; } 2，滾動數組 [html] #include<iostream> #include<stdio.h> #include<string.h> using namespace std; int main() { int a[5001]; int b[5001]; int dp[10][5001]; int i,j; int n; char str; cin>>n; getchar(); for(i=1;i<=n;i++) { scanf("%c",&str); a[i]=str; b[n-i+1]=str; } dp[1][0]=dp[0][0]=0; for(i=0;i<=n;i++) { dp[0][i]=0; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { dp[i%2][j]=max(dp[i%2][j-1],dp[(i-1)%2][j]); if(a[i]==b[j]) { dp[i%2][j]=max(dp[i%2][j],dp[(i-1)%2][j-1]+1); } } } int len; len=dp[n%2][n]; printf("%d\n",n-len); return 0; }
