证明
分析这个问题需要带入y总的分析方法来看。先找到前后的关系,然后初始化一开始的部分。然后在循环的过程中用前面的来求后面的。
我们如果这个题也这么想的话,只能把f[i][j]看成s1的前i个转化成s2的前j个操作了多少次然后分析s1的第i个字母和前面的关系。
那么就这么想吧,对于循环来说我们可以想到每一位要么变要么删除,也么不动,要么加不知道多少位(!),这里是重点,因为视频里面y总的讲解直接默认每一位只加一位
,这其实是有一点不顺畅的
完整的讨论应该是,f[i][j]在s1[i]这1位怎么做才能得到最小值呢?
1.如果要删除这一位才能得到最小值的话,f[i][j]=f[i-1][j]+1;
2.如果要更改才能得到最小值的话,f[i][j]=f[i-1][j-1]+1; 要求s1[i]!=s2[j]
3.不需要动直接加上就能得到最小值的话: f[i][j]=f[i-1][j-1] 要求s1[i]==s2[j]
4.在s1[i]后面要加x位字母才能得到最小值的话:f[i][j] = f[i][j-x]+x,保证j-x>=0,具体做需要很多x做法求min
这样的讨论是完备的,因为他就像01问题一样全面,每一位只有这么多选择,所以可以放心的求最小值就好了。
y总的讲解里面第四部分只用了x==1,并且通过了,说明一定是1比选择其他的x都要小所以才可以省略。
我们这里来证明一下:
我们假设x1小于x2并且j-x1>=0,j-x2>=0
只要证明f[i][j-x1]+x1<=f[i][j-x2]+x2就可以得到只需要写x==1的部分了,毕竟除了0,1是最小的,而x==0就一个数都没有加也不属于我们的讨论范畴了
而上式等价于
f[i][j-x1]-f[i][j-x2]<=x2-x1
令m = j - x1
原式化为f[i][m]-f[i][m+x1-x2]<=x2-x1
也就是 f[i][m]-f[i][m-(x2-x1)]<=x2-x1
单纯这个式子的意思就是s1前i个字母转化成s2的前m个字母的操作次数最多比s1前i个字母转化成转化成s2的前m-(x2-x1)个字母的操作次数多(x2-
x1)
我们用反证法证明他的正确性:
假如说这个次数之差>x2-x1,即f[i][m]-f[i][m-(x2,x1)]>x2-x1
即 f[i][m]>f[i][m-(x2,x1)]+x2-x1
问题来了,仅对于这个式子我们可以发现右边其实可以这么理解:先把s1的前i个转化为s2的前m-(x2-x1),并且花费的是最少次数f[i][m-(x2-x1)]
然后再通过x2-x1次加字母加成s2的前m个字母,也就是说右边其实是我们总体i,m转化的一种方式,其次数甚至可能并不是转化的最小值,但是这个式子
却写着他小于最小值?所以不存在这种情况,所以一切证明完毕,我们证明出了确实可以只写x==1的情况
证完就可以写代码了,大家觉得有点用的话可以点个赞hh
#include<iostream>
using namespace std;
const int N = 1010;
char s1[N],s2[N];
int n1,n2;
int f[N][N];
int main()
{
cin>>n1>>s1+1>>n2>>s2+1;
for(int i=0;i<=n1;i++)
{
for(int j=0;j<=n2;j++)f[i][j]=2010;//先让每一个f[i][j]都特别大,否则都是0的话我们后面取min就变成小丑了
}
for(int i=0;i<=n2;i++)f[0][i]=i;
for(int i=1;i<=n1;i++)f[i][0]=i;//这一步初始化不是凭空想出来的,而是我们看到都是在往前求,我们一定要他一个支点,不让他无穷尽的往前
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
f[i][j]=min(f[i-1][j]+1,f[i][j]);//第一种
f[i][j]=min(f[i][j],f[i][j-1]+1);//第4种,23要讨论所以我们放到最后
if(s1[i]==s2[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
}
cout<<f[n1][n2];
return 0;
}