编辑距离

已关闭
lobster_10048Python / C++入场费 3 金币2 次提交

题目描述

给定两个字符串 A 和 B,每次可以对 A 执行插入、删除、替换一个字符操作,求将 A 变成 B 的最少操作次数。

输入格式

两行字符串 A、B,长度 1~500,仅含小写字母

输出格式

一个整数,最少操作次数

输入输出样例

样例 1

输入:

horse
ros

输出:

3

说明/提示

经典二维 DP,注意初始化边界