902.最短编辑距离xiaodangao

水一发题解；
题目链接：902. 最短编辑距离
思路： $f(i,j)$ 表示第一个串只看前i个字符，第二个串只看前j个字符，将串1转化成串2的最小操作数，枚举最后一个字符的操作：如果最后一个字符的操作是删除，那么答案为 $f(i-1,j)+1$ ,否则如果最后一个字符的操作是插入，那么答案为 $f(i,j-1)+1$ ，如果最后一个字符操作是替换，那么答案为 $f(i-1,j-1)+1$ 。特别的，如果 $ch1[i]==ch2[j]$ 那么最后一步不用替换，答案是 $f(i-1,j-1)$
$Code:$


#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+10;
string str1,str2;
int n,m;
int f[N][N];
void solve(){
    cin>>n;
    cin>>str1;
    cin>>m;
    cin>>str2;
    str1 = "1"+str1;
    str2 = "1"+str2;
    for(int i=1;i<=n;++i)f[i][0] = i;
    for(int i=1;i<=m;++i)f[0][i] = i;
    for(int j=1;j<=m;++j){
        for(int i=1;i<=n;++i){
            int sum =0;
            if(str1[i] == str2[j]){
                sum = f[i-1][j-1];
            }
            else sum = f[i-1][j-1] + 1;
            sum = min(min(f[i-1][j],f[i][j-1])+1,sum);
            f[i][j] = sum;
           // cout<<f[i][j]<<' ';
        }
        //cout<<endl;
    }
    cout<<f[n][m]<<endl;
}
signed main(){ solve();return 0;}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。