文章

5

粉丝

221

获赞

12

访问

25.4k

头像
套公式题解(C++dp)

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int dp[MAX][MAX];
string a,b;
//dp[i][j]是指字符串1中的前i个字符和字符串2中的前j个字符的编辑距离

int main(){
    cin>>a>>b;
    int lena = a.length();
    int lenb = b.length();
    memset(dp, 0, sizeof(dp));

    //initialization
    for(int i=0;i<lena;i++) dp[i][0]=i;
    for(int i=0;i<lenb;i++) dp[0][i]=i;

    //套公式
    int t1=0, t2=0;
		//注意代码中的两层循环时从1开始的,从而使得i-1和j-1不需要特殊处理
    for(int i=1;i<=lena;i++){
        for(int j=1;j<lenb;j++){
            t1 = 1 + min(dp[i][j-1], dp[i-1][j]);
            if(a[i-1]==b[j-1])  t2 = dp[i-1][j-1];
            else    t2 = dp[i-1][j-1] + 1;
            dp[i][j] = min(t1,t2);
        }
    }
    cout<<dp[lena-1][lenb-1]<<endl;
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发