POJ 3356.AGTC

问题简述:

  输入两个序列x和y,分别执行下列三个步骤,将序列x转化为y

  (1)插入;(2)删除;(3)替换;

  要求输出最小操作数。

  原题链接:http://poj.org/problem?id=3356

解题思路:

  明显的动态规划题,输入两个字符串 a[0...m-1] , b[0...n]

  使用二维数组 dp[i,j] 记录 a[0...i] 和 b[0...j] 对应的最小操作数

  显然有以下递归方程:

  dp[i,0] = i

  dp[0,j] = j

  dp[i,j] = dp[i-1,j-1]     if a[i-1]==b[j-1]

  dp[i,j] = min(dp[i-1,j-1],dp[i-1,j],dp[i,j-1]) + 1    if a[i-1]!=b[j-1]

源代码

 1 /*
 2 OJ: POJ
 3 ID: 3013216109
 4 TASK: 3356.AGTC
 5 LANG: C++
 6 NOTE: DP
 7 */
 8 #include <cstdio>
 9
10 const int MAX=1005;
11 int m,n,i,j,k;
12 char a[MAX],b[MAX];
13 int dp[MAX][MAX],c[MAX];
14
15 int min(int x,int y,int z) {
16     if(x<+y&&x<=z)
17         return x;
18     if(y<=x&&y<=z)
19         return y;
20     if(z<=x&&z<=y)
21         return z;
22 }
23
24 int main()
25 {
26     while(scanf("%d %s",&m,a)!=EOF) {
27         scanf("%d %s",&n,b);
28         for(i=0;i<=m;i++)
29             dp[i][0]=i;
30         for(j=0;j<=n;j++)
31             dp[0][j]=j;
32         k=0;
33         for(i=1;i<=m;i++) {
34             for(j=1;j<=n;j++) {
35                 if(a[i-1]==b[j-1])
36                     dp[i][j]=dp[i-1][j-1];
37                 else
38                     dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
39             }
40         }
41         printf("%d\n",dp[m][n]);
42     }
43     return 0;
44 }
时间: 06-01

POJ 3356.AGTC的相关文章

POJ 3356 AGTC 最短编辑距离 DP

http://poj.org/problem?id=3356 题意: 给两个长度不大于1000的串,修改其中一个串使得两串相同,问最少修改次数.修改有三种,插入一个字符,删除一个字符,改变一个字符. 分析: 直接给方程. dp[i][j]表示第一个串前i位和第二串前j位匹配的最小修改次数. dp[0][0] = 0, dp[length(x)][length(y)]为答案. dp[i][j] = min(dp[i-1][j-1] + x[i] != y[j], dp[i-1][j] + 1, d

POJ 3356 AGTC(最长公共子序列)

AGTC Description Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below: Deletion: a letter in x is missing in y at a corresponding position. Insertion: a letter in y is missin

POJ 3356 AGTC(DP-最小编辑距离)

Description Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below: Deletion: a letter in x is missing in y at a corresponding position. Insertion: a letter in y is missing in 

POJ 3356 AGTC (编辑距离 DP)

Description Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below: Deletion: a letter in x is missing in y at a corresponding position. Insertion: a letter in y is missing in

POJ 3356 AGTC(最小编辑距离)

http://poj.org/problem?id=3356 题意: 给出两个字符串x 与 y,当中x的长度为n,y的长度为m,而且m>=n.然后y能够经过删除一个字母,加入一个字母,转换一个字母,三种操作得到x.问最少能够经过多少次操作 分析: 我们令dp[i][j]==x表示源串的前i个字符变成目串的前j个字符须要x步操作. 初始化: dp[0][i]==i且 dp[i][0]=i. 上述前者表示加入源串i个字符, 后者表示删除源串i个字符. 状态转移: dp[i][j]假设我们仅仅在源串的

POJ 3356 AGTC(DP求字符串编辑距离)

给出两个长度小于1000的字符串,有三种操作,插入一个字符,删除一个字符,替换一个字符. 问A变成B所需的最少操作数(即编辑距离) 考虑DP,可以用反证法证明依次从头到尾对A,B进行匹配是不会影响答案的 令dp[i][j]表示A[i]~[lenA]变成B[j]~[lenB]的最优解. 如果把B[j]插入到A[i]前,dp[i][j]=dp[i][j+1]+1 如果删除A[i],dp[i][j]=dp[i+1][j]+1. 如果A[i]==B[j], dp[i][j]=dp[i+1][j+1].

poj 3356

Description Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below: Deletion: a letter in x is missing in y at a corresponding position. Insertion: a letter in y is missing in

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 *

POJ - 3186 Treats for the Cows (区间DP)

题目链接:http://poj.org/problem?id=3186 题意:给定一组序列,取n次,每次可以取序列最前面的数或最后面的数,第n次出来就乘n,然后求和的最大值. 题解:用dp[i][j]表示i~j区间和的最大值,然后根据这个状态可以从删前和删后转移过来,推出状态转移方程: dp[i][j]=max(dp[i+1][j]+value[i]*k,dp[i][j-1]+value[j]*k) 1 #include <iostream> 2 #include <algorithm&