【POJ3356】AGTC (动态规划dp+最长公共子序列lcs)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 22 日

一个字符串可以插入、删除、改变到另一个字符串,求改变的最小步骤。和最长公共子序列类似,用二维数组opt[i][j]记录字符串a中的前i个字符到字符串b中的前j个字符匹配所需要的最小步数。假如已知AG到GT的最小步数,AGT到GT的最小步数,AG到GTT的最小步数,求AGT到GTT的最小步数,此时T= =T,这个值是AG到GT的最小步数,AGT到GT的最小步数加一(AGT到GT的最小步数等于AGTT到GTT的最小步数,加一是将T删除的一步),AG到GTT的最小步数加一(AG到GTT的最小步数等于AGT到GTTT的最小步数,加一是在AGT上增加T的一步)。假如已知AG到GT的最小步数,AGA到GT的最小步数,AG到GTT的最小步数,求AGA到GTT的最小步数,此时A! =T,这个值是AG到GT的最小步数加一(A改变为T),AGA到GT的最小步数加一(AGA到GT的最小步数等于AGAT到GTT的最小步数,加一是将T删除的一步),AG到GTT的最小步数加一(AG到GTT的最小步数等于AGA到GTTA的最小步数,加一是在GTTA上删除A的一步)。所以状态转移方程:
if(str1.charAt(i-1)==str2.charAt(j-1))
array[i][j] = Math.min(Math.min(array[i-1][j-1], array[i-1][j]+1), array[i][j-1]+1);
else
array[i][j] = Math.min(Math.min(array[i-1][j-1]+1, array[i-1][j]+1), array[i][j-1]+1);
初始化的时候和最长公共子序列不同,因为第0行,第0列表示null转化到字符串情况,结果是字符串的长度:

for(int i=0;i<=m;i++){

array[i][0] = i;

}

for(int i=0;i<=n;i++){

array[0][i] = i;

}

  Null A G T G A T G
Null 0 1 2 3 4 5 6 7
G 1              
T 2              
T 3              
A 4              
G 5              

结果是array[m][n]

 

下边代码poj又是无限错。。。。郁闷啊,继续求教育啊~~~希望有人指出。

#include <iostream>  
#include <string>  
#include <algorithm>  
using namespace std;  
int arr[1005][1005];  
int main(){  
    freopen("1.txt","r",stdin);  
    string st1,st2;  
    int n,m;  
    for (int i=0;i<=1001;i++)  
    {arr[i][0]=i;arr[0][i]=i;}  
    while(!cin.eof()){  
        cin>>n;if(n!=0)cin>>st1;  
        cin>>m;if(m!=0)cin>>st2;  
        for (int i=1;i<=n;i++)  
            for (int j=1;j<=m;j++)  
                    arr[i][j]=min( arr[i-1][j-1]+(st1[i-1]!=st2[j-1]), min( arr[i-1][j]+1,arr[i][j-1]+1 ));  
        cout<<arr[n][m]<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日