364. 最短编辑距离
时间限制：1000 MS 内存限制：64 MB
题目描述
# 最短编辑距离 ## 题目描述 给定两个字符串 $A$ 和 $B$，你需要通过若干次操作将 $A$ 变为 $B$。每次可以对当前字符串进行以下三种操作之一： 1. **删除**：删除一个字符。 2. **插入**：在任意位置插入一个字符，包括字符串的开头或末尾。 3. **替换**：将一个字符替换为另一个字符。 每次操作的代价均为 $1$。请你求出将 $A$ 变为 $B$ 所需的最少操作次数。 ## 输入格式 从文件 `edit.in` 中读入数据。 输入共四行： - 第一行包含一个整数 $n$，表示字符串 $A$ 的长度。 - 第二行包含一个长度为 $n$ 的字符串 $A$。 - 第三行包含一个整数 $m$，表示字符串 $B$ 的长度。 - 第四行包含一个长度为 $m$ 的字符串 $B$。 ## 输出格式 将答案输出到文件 `edit.out` 中。 输出一个整数，表示将 $A$ 变为 $B$ 所需的最少操作次数。 ## 数据范围 - $1 \le n,m \le 1000$。 - 字符串 $A$ 和 $B$ 均仅包含大写英文字母。 ## 样例输入 ``` 10 AGTCTGACGC 11 AGTAAGTAGGC ``` ## 样例输出 ``` 4 ``` ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$64$ MB。