POJ 3356 AGTC

【类型】

动态规划:编辑距离

【题目来源】

POJ-3356-AGTC

【思路来源】

可笑痴狂

【思路】

状态转移方程:
有三种情况可以导致我们上面设计的状态会发生转移。我们现在来看A[i] 和 B[j] ,
①、我们可以在 B[j]后面插入一个核苷酸(即一个字符)ch,ch==A[i],这样做的话,
至少需要 dp[i – 1][j] + 1步操作,即 dp[i][j] = dp[i – 1][j] + 1。
②、我们可以删除 B[j],这样的话,B[1…j] 变为A[1…i] 需要 dp[i][j – 1]步,
即 dp[i][j] = dp[i][j – 1] + 1。
③、我们也可以考虑修改 B[j],使它变为A[j],但是如果 B[j]本来就等于 A[i]的话,
那修改其实相当于用了 0步,如果 B[j] != A[i] 的话,那修改相当于用了 1步。
所以 dp[i][j] = dp[i – 1][j – 1] + (A[i] == B[j] ? 0, 1)。

决策:
决策就很简单了,从上面三种状态转移中选择一个最小值就可以了。

处理边界:
处理好边界非常重要,这里需要注意的是对dp[0][0….m],dp[0…..n][0]的初始化,
可以这样看,dp[0][i],就是说A[1…n]是一个空串,而B[1…m]十个长度为i的串,
很显然B串变为A串就是删除i个核苷酸。

【Code】

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
char s1[1005],s2[1005];
int dp[1005][1005];
int s1l,s2l;

int DP(){
        for(int i=0;i<s1l;++i){
            for(int j=0;j<s2l;++j){
                if(s1[i]==s2[j])
                    dp[i+1][j+1]=min(min(dp[i+1][j]+1,dp[i][j+1]+1),dp[i][j]);
                else
                    dp[i+1][j+1]=min(min(dp[i+1][j]+1,dp[i][j+1]+1),dp[i][j]+1);
            }
        }
    return dp[s1l][s2l];
}

void init(){
    memset(dp,0,sizeof(dp));
    int tmp=max(s1l,s2l);
    for(int i=1;i<=tmp;++i)
        dp[i][0]=dp[0][i]=i;
}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>s1l>>s1){
        cin>>s2l>>s2;
        init();
        cout<<DP()<<endl;
    }
    return 0;
}