编辑距离

题目描述

给定两个字符串 $s$ 与 $t$，请计算 $s$ 到 $t$ 的编辑距离。所谓编辑距离，就是最少进行多少步修改可以将 $s$ 变成 $t$，每次修改操作可以从以下操作选择一种：

• 插入一个字符
• 删除一个字符
• 替换一个字符

编辑距离是一个很重要的概念，比如：

• 微信公众号有个规定：已经发表的文章，只能修改 2020 个字。所以公众号的运营人员需要仔细计算新旧文章的编辑距离。
• DNA 是由 actg 四个字母组成的字符串，编辑距离可以规划编辑 DNA 的最佳方案。

输入格式

• 第一行：一个字符串 $s$，由小写英文字符组成
• 第二行：一个字符串 $t$，由小写英文字符组成

输出格式

• 单个整数：表示两个字符串的编辑距离

样例输入 #1

atcg
tcga

样例输出 #1

2

样例说明 #1

删除第一个 a，然后在字符串尾部再加一个 a。

样例输入 #2

abcdefg
gfedcba

样例输出 #2

6

数据范围

• $1\le |s|\le 2000$
• $1\le |t|\le 2000$

测试点分布