【线性DP】最短编辑距离

题目

902. 最短编辑距离

---

给定两个字符串 $A$ 和 $B$ ，现在要将 $A$ 经过若干操作变为 $B$ ，可进行的操作有：

1. 删除–将字符串 $A$ 中的某个字符删除。
2. 插入–在字符串 $A$ 的某个位置插入某个字符。
3. 替换–将字符串 $A$ 中的某个字符替换为另一个字符。

现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。

输入格式

第一行包含整数 $n$ ，表示字符串 $A$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $A$ 。

第三行包含整数 $m$ ，表示字符串 $B$ 的长度。

第四行包含一个长度为 $m$ 的字符串 $B$ 。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

$1 \le n, m \le 1000$

输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

解题

方法一：动态规划

思路

思维过程：

动态规划：

• 状态定义：$dp[i][j]$ 表示把「字符串 $A$ 中前 $i$ 个字符组成的序列」变成「字符串 $B$ 中前 $j$ 个字符组成的序列」的所有方案中操作数最小的。

• 状态转移方程：

  $$dp[i][j] = \min \begin{cases} dp[i - 1][j] + 1 \\ dp[i][j - 1] + 1 \\ \begin{cases} dp[i - 1][j - 1] & A[i] = B[j] \\ dp[i - 1][j - 1] + 1 & A[i] \neq B[j] \end{cases} \end{cases}$$

• 初始状态：

  • 把「字符串 $A$ 中前 $0$ 个字符组成的序列」变成「字符串 $B$ 中前 $j$ 个字符组成的序列」时只能增加，操作数为 $j$，所以 $dp[0][j] = j$（$j = 0 \dots m$）。
  • 把「字符串 $A$ 中前 $i$ 个字符组成的序列」变成「字符串 $B$ 中前 $0$ 个字符组成的序列」时只能删除，操作数为 $i$，所以 $dp[i][0] = i$（$i = 0 \dots n$）。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine().trim());
        char[] a = (' ' + in.readLine()).toCharArray();
        int m = Integer.parseInt(in.readLine().trim());
        char[] b = (' ' + in.readLine()).toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= m; ++i) dp[0][i] = i;
        for (int i = 0; i <= n; ++i) dp[i][0] = i;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                if (a[i] == b[j]) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                else dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        System.out.println(dp[n][m]);
    }
}