最短编辑距离——线性dp

902. 最短编辑距离 - AcWing题库

刚拿到题感觉无从下手。看了讲解之后才领悟了一丢丢。既然题目是问操作次数的最小值，那么我们就把每一次可以进行的操作分一下类。

首先还是按照y总的方法，先分析出状态表示。因为题中问的是将A变成B需要的操作次数，所以我们的状态表示可以是为了让A的前i个字符与B的前j个字符相同的操作次数。求的是最小值min。

对于状态计算，我们可以把f [ i , j ]按照操作的方式进行划分。dp都是分析该状态下最后一个不同的操作。

1.删除–将字符串 A">A中的某个字符删除：

A">　　注意dp分析的是最后一个不同的操作，已经默认前面的都是最优状态了。所以对于删除操作，我们已经默认A的前i-1个字符与B的前j个字符相同了，此时操作加一，就是删除操作了。

A">　　因此f[i,j]=f[i-1,j]+1。

A">2.插入–在字符串 A">A的某个位置插入某个字符：

A">A">　　对于插入操作，我们默认前i与j-1相同，现在只需要插入一个字符，使得第i个字符（新插入的字符)与第j个字符相等即可。

A">A">　　因此f[i,j]=f[i][j-1]+1。

A">A">3.替换–将字符串 A">A 中的某个字符替换为另一个字符：

A">　　对于插入操作，我们已经默认前i-1与j-1相同，只需要将第i个字符替换成和第j个字符相同的字符即可

A">　　因此f[i,j]=f[i-1][j-1]+1

A">4.什么也不做

A">　　如果第i字符与第j字符相等，那就什么也不做，操作次数不变

A">　　因此f[i,j]=f[i-1,j-1]

A">但是我们还要考虑边界问题。当j=0的时候，表示的含义是前i个字符要与0个字符匹配相同，也就是要把前i个字符全部删除，而全部删除的操作次数为i次。因此刚开始的时候应该遍历初始化f[i][0]=i;当i=0的时候，表示的含义是前0个字符与前j的字符相匹配，也就是插入j个字符,操作次数为j次。因此刚开始的时候应该遍历初始化f[0][j]=j

 1 #include 
 2 using namespace std;
 3 const int N=1e3+100;
 4 char a[N],b[N];
 5 int f[N][N];
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%s",&n,a+1);
10     scanf("%d%s",&m,b+1);
11     for(int i=1;i<=n;i++)f[i][0]=i;        //全部删除
12     for(int i=1;i<=m;i++)f[0][i]=i;        //全部插入
13     
14     for(int i=1;i<=n;i++)
15     {
16         for(int j=1;j<=m;j++)
17         {
18             f[i][j]=min(f[i][j-1],f[i-1][j])+1;
19             if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
20             else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
21         }
22     } 
23     
24     printf("%d\n",f[n][m]);
25     return 0;
26 }