首页 > 代码库 > poj3356 AGTC(经典DP最小编辑距离)
poj3356 AGTC(经典DP最小编辑距离)
题目意思:
给出两个字符串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<stdio.h> #include<string.h> 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; }
poj3356 AGTC(经典DP最小编辑距离)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。