题目描述
给定两个字符串A和B,现在要将A经过若干操作变为B,可进行的操作有:
删除–将字符串A中的某个字符删除。
插入–在字符串A的某个位置插入某个字符。
替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出,将A变为B至少需要进行多少次操作。
输入格式
第一行包含整数n,表示字符串A的长度。
第二行包含一个长度为n的字符串A。
第三行包含整数m,表示字符串B的长度。
第四行包含一个长度为m的字符串B。
字符串中均只包含小写字母。
输出格式
输出一个整数,表示最少操作次数。
数据范围
1≤n,m≤1000
样例
输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4
如何去想(代码就不发了,去COPY大佬的就可以了)
一般来说,我们做dp,想的是当前状态由谁转移过来
换一种思路----当前状态可以去转移谁
结合例题,题目给了我们三种操作,删、插、换
设当前状态为dp[i][j](i:表示a数组中第i个位置,j:表示b数组是第j个位置)
(开始表演)
1、如果把a[i]删掉,那么,b[j]将会和a[i+1]比较,体现在动态数组dp[i][j]上的是,当前dp[i][j]的值,会对dp[i+1][j]产生影响,用数学公式表示,即为dp[i+1][j]=dp[i][j]+1;
2、如果在a[i]位置插入一个数,那么,a[i]将会和b[j+1]比较(插入的字母肯定和b[j]一样),体现在动态数组dp[i][j]上的是,当前dp[i][j]的值,会对dp[i][j+1]产生影响,用数学公式表示,即为dp[i][j+1]=dp[i][j]+1;
3、如果把a[i]换掉,那么,b[j]将会和a[i]比较,体现在动态数组dp[i][j]上的是,当前dp[i][j]的值,会对dp[i+1][j+1]产生影响。这里要注意的是,如果a[i]和b[j]相等的话,就可以不用操作这一步,但仍会对f[i][j]产生影响,只不过,这种影响相当于没有影响。用数学公式表示f[i+1][j+1]=f[i][j]或f[i+1][j+1]=f[i][j]+1;
然后我们在把思路反转过来
f[i][j]可以由谁转移过来
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1](或f[i-1][j-1]+1));
在看下一个问题
为啥要初始化(我也有点绕~_~,有更好的想法留言啊)
1、当i>j的时候,尤其是j==0的时候,怎样才能让a[i]和b[j]匹配,只要把a数组中1~i上的所有数据删了就可以了,需要i步操作
2、当i<j的时候,同上,只不过是往a中插入数据