问题 2774 --Edit

2774: Edit

时间限制: 1 Sec  内存限制: 128 MB
提交: 128  解决: 44
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

  有二个字串 str1, str2 , 字串str2 可以经过若于次变换后变成str1,其变换的规则是:

  1) 可以在任何位置加入字符;

  2) 可以删除任何字符;

  3) 可以改变任何字符。

  约定:增加、删除与改变任何一个字符称为一次变换。

  例如:str1=‘bcadef ’           str2=’abcedkk’ 

  可以经过的变换为:

  1)删去第一个字符‘a’                     str2=’bcedkk’

  2)改变一个字符,将‘e’变成‘a’          str2=’bcadkk’

  3)改变一个字符,将‘k’变成‘e’          str2=’bcadek’

  4) 改变一个字符,将‘k’变成‘f’          str2=’bcadef’

  此时,str2 经过4次变换后变成str1。

  问题:给出str1,str2,要求用最少的变换次数从str2变换为str1 。

输入

  多笔测资,每笔测资两行

  第一行:字符串s1

  第二行:字符串s2

输出

  对每笔测资,输出一个整数,表示该组的最少变换次数。

样例输入

bcadef
abcedkk

样例输出

4

提示

动态规划

来源

[提交][状态]