AcWing 902. java同学
原题链接
简单
作者:
季之秋
,
2021-02-10 17:03:53
,
所有人可见
,
阅读 215
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
String a=" "+sc.next();
int m=sc.nextInt();
String b=" "+sc.next();//加空格 下标从1开始
int N=1010;
int f[][]=new int[N][N];
for(int i=0;i<N;i++){ //初始化边界的状态,一般看数组里取到0和1的情况,
f[0][i]=f[i][0]=i; //因为f[0][i]!=0 而且f[0][i]=f[i][0]=i,所以需要初始化
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=Math.min(f[i-1][j]+1,f[i][j-1]+1);
f[i][j]=Math.min(f[i][j],a.charAt(i)==b.charAt(j)?f[i-1][j-1]:f[i-1][j-1]+1);
//如果两个值相同就不需要替换操作,否则就加一步替换操作
}
}
System.out.println(f[n][m]);
}
}