| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 44186 | Accepted: 15050 |
Description
Input
Output
Sample Input
5 Ab3bd
Sample Output
2
输入a串，求其变成回文串所要进行的插入或删除操作的最少的步骤
Dp[i][j] 为a[i~j] 子串变为回文串所要进行插入或删除的操作的最少步骤。
Min{dp[i][j-1]+1, dp[i-1][j]+1} (a[i]!=a[j])
Dp[i][j]=
Min{dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]} (a[i]==a[j])
则最后答案为dp[1][n]
#include<cstdio> #include<string> #include<iostream> #include<cstring> #include<algorithm> using namespace std; short dp[5001][5001]; int n; string s; int main(){ while(cin>>n>>s){ memset(dp,0,sizeof(dp)); for(int i=n-1;i>=0;i--){ for(int j=i;j<n;j++){ if(s[i]==s[j])dp[i][j]=dp[i+1][j-1]; else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1; } } printf("%d\n",dp[0][n-1]); } return 0; }
原文：http://www.cnblogs.com/demodemo/p/4732574.html
