Edit Distance

题目描述

两个字符串之间的编辑距离是将一个字符串变换为另一个字符串所需的最少操作次数。 允许的操作是： 例如，字符串 LOVE 和 MOVIE 之间的编辑距离为 2，因为你可以先将 L 替换为 M，然后再添加 I。 你的任务是计算两个字符串之间的编辑距离。

输入格式

第一行输入是一个包含 n 个字符的字符串，字符范围为 A–Z。 第二行输入是一个包含 m 个字符的字符串，字符范围为 A–Z。

输出格式

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

LOVE
MOVIE

2

提示

$1 \le n,m \le 5000$

标签: CSES1639|动态规划|DP

来源

CSES1639|动态规划|DP