Problem 2774 --Edit

2774: Edit

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 128  Solved: 44
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

  有二个字串 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 。

Input

  多笔测资,每笔测资两行

  第一行:字符串s1

  第二行:字符串s2

Output

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

Sample Input

bcadef
abcedkk

Sample Output

4

HINT

动态规划

Source

[Submit][Status]