侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【线性DP】最短编辑距离

GabrielxD
2022-11-29 / 0 评论 / 0 点赞 / 25 阅读 / 813 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

902. 最短编辑距离


给定两个字符串 AABB ,现在要将 AA 经过若干操作变为 BB ,可进行的操作有:

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

现在请你求出,将 AA 变为 BB 至少需要进行多少次操作。

输入格式

第一行包含整数 nn ,表示字符串 AA 的长度。

第二行包含一个长度为 nn 的字符串 AA

第三行包含整数 mm ,表示字符串 BB 的长度。

第四行包含一个长度为 mm 的字符串 BB

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

输出格式

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

数据范围

1n,m10001 \le n, m \le 1000

输入样例:

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例:

4

解题

方法一:动态规划

思路

思维过程:

image-20221128235652688

动态规划:

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

  • 状态转移方程:

    dp[i][j]=min{dp[i1][j]+1dp[i][j1]+1{dp[i1][j1]A[i]=B[j]dp[i1][j1]+1A[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}

  • 初始状态:

    • 把「字符串 AA 中前 00 个字符组成的序列」变成「字符串 BB 中前 jj 个字符组成的序列」时只能增加,操作数为 jj,所以 dp[0][j]=jdp[0][j] = jj=0mj = 0 \dots m)。
    • 把「字符串 AA 中前 ii 个字符组成的序列」变成「字符串 BB 中前 00 个字符组成的序列」时只能删除,操作数为 ii,所以 dp[i][0]=idp[i][0] = ii=0ni = 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]);
    }
}
0

评论区