链接: https://cses.fi/problemset/task/1639

板块: Dynamic Programming

时限: 1.00 s ｜ 内存: 512 MB

题目描述

两个字符串之间的编辑距离是指将其中一个字符串转换成另一个字符串所需的最少操作次数。

允许的操作有：

• 在字符串中添加一个字符。
• 从字符串中删除一个字符。
• 将字符串中的一个字符替换成另一个字符。

例如，LOVE 和 MOVIE 之间的编辑距离为 $2$，因为你可以先把 L 替换为 M，再添加 I。

你的任务是计算两个字符串之间的编辑距离。

输入

第一行输入包含一个字符串，其中包含 $n$ 个 A–Z 之间的字符。

第二行输入包含一个字符串，其中包含 $m$ 个 A–Z 之间的字符。

输出

输出一个整数：字符串之间的编辑距离。

数据范围

$1 \le n,m \le 5000$

样例输入

LOVE
MOVIE

样例输出

2