題目意思:
給出兩個字符串X,Y,求出從X——>Y的最小操作次數,只可以刪除,添加,修改一個字符。
http://poj.org/problem?id=3356
題目分析:
/** *x,y:是字符串 *動態規劃最小編輯距離, *dp[i][j]表示取x的前i個字符和y的前j個字符操作的最小次數。 *dp[0][j]=j:取x的前0個字符和y的前j個字符操作的 *最小次數為(j),只能添加到x * *dp[i][0]=i:取x的前i個字符和y的前0個字符操作的 *最小次數為(i),只能刪除x * *dp[i][j]只有三種來源: *1、由x刪除一個字符得到:dp[i][j]=dp[i-1][j]+1; *2、由x添加一個字符得到(相當於y刪除一個):dp[i][j]=dp[i][j-1]+1; *3、由轉換得到:if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]; * else dp[i][j]=d[i-1][j-1]+1; *dp[i][j]取到三種操作中的最小次數: *str1[i-1]==str2[j-1]?ok=1:ok=0; *轉化方程: *dp[i][j]=min(dp[i-1][j-1]+ok,dp[i-1][j]+1,dp[i][j-1]+1); */
AC代碼:
#include#include int dp[1005][1005]; char str1[1005],str2[1005]; int min(int a,int b,int c){ int min=a; if(min>b) min=b; if(min>c) min=c; return min; } int main() { int n,m; while(scanf("%d%s",&n,str1)==2){ scanf("%d%s",&m,str2); for(int i=0;i<=n;i++) dp[i][0]=i;//初始化str1前i個字符轉化為str2的前0字符的操作數 for(int j=0;j<=m;j++) dp[0][j]=j;//初始化str1前0個字符轉化為str2的前j字符的操作數 int ok; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ str1[i-1]==str2[j-1]?ok=0:ok=1; dp[i][j]=min(dp[i-1][j-1]+ok,dp[i-1][j]+1,dp[i][j-1]+1); } } printf("%d\n",dp[n][m]); } return 0; }