题目描述
算法1
(动态规划) $O(n^2)$
dp[i][j]
表示 a[0,i-1] 变成 b[0,j-1] 的操作步数-
if(a[i-1]==b[i-1])
表示此时 无需操作,dp[i][j]=dp[i-1][j-1]
如果不相等,则考虑增加,删除,和修改 三种操作 ,取最小值。
增加dp[i][j]=dp[i][j-1] +1
删除dp[i][j]=dp[i-1][j] +1
修改dp[i][j]=dp[i-1][j-1] +1
-
考虑初始化的问题,
dp[i][0] =i
a 的长度为 0, b 的长度为 i ,此时应该进行 i 次删除。 同理dp[0][j]=j
时间复杂度
$O(n^2)$
参考文献
算法基础课
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int N=1010;
static int[][]dp=new int[N][N];
static int n,m;
static char[] word1,word2;
public static void main(String[] args) throws IOException {
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
// n 后面带一个 空格
n = Integer.parseInt(reader.readLine().split(" ")[0]);
word1=reader.readLine().toCharArray();
m = Integer.parseInt(reader.readLine().split(" ")[0]);
word2=reader.readLine().toCharArray();
int len1=word1.length;
int len2 =word2.length;
for(int i=0;i<=len1;i++){
dp[i][0]=i;
}
for(int j=0;j<=len2;j++){
dp[0][j]=j;
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
}
}
}
// for(int i=0;i<=len1;i++){
// for(int j=0;j<=len2;j++){
// System.out.print(dp[i][j]+" ");
// }
// System.out.println(" ");
// }
System.out.println(dp[len1][len2]);
}
}