编辑距离

p2758-编辑距离

思路：
用f[i][j]表示第一个字符串的前 i 个字母变为第二个字符串的前 j 个字母所用的最少操作次数。

假设第一个字符串为：AGTCTGACGC

第二个字符串为：AGTAAGTAGGC

f[3][5] 表示把第一个字符串的前三个字母变为第二个字符串的前五个字母所需要的最少操作次数。

也就是把AGT变为AGTAA所用的最少操作次数。

分析递推方程：

把第一个字符串的前 i 个字母变为第二个字符串的前 j 个字母，有三种方法：

把第一个字符串的前 i 个字母变为第二个字符串的前 j - 1 个字符，然后在第一个字符串后面增加第二个字符串的第j个字母。

这种情况下，f[i][j] = f[i][j - 1] + 1。

例如：把AGT变为AGTAA，可以先把AGT变为AGTA，然后再在最后面添加一个字符A。

把第一个字符串的前 i - 1 个字母变为第二个字符串的前 j 个字符，然后去掉最后一个字符。

例如：把AGT变为AGTAA，可以先把AGT变为AGTAAT，然后再去掉一个字符T。

这种情况下，f[i][j] = f[i - 1][j] + 1。

把第一个字符串的前 i - 1 个字母变为第二个字符串的前 j - 1个字符。变化之后，对比最后一个字符，如果相等，则变换完成，如果不同，把第一个字符串的最后一个字符变为第二个字符串的最后一个字符，

例如：把AGT变为AGTAA，可以先把AGT变为AGTAT，然后再在最后面添加一个字符T变为A。

例如：把AGT变为AGTAT，可以先把AGT变为AGTAT，因为最后一个字符相同，不再做处理。

这种情况下，f[i][j] = f[i - 1][j - 1] + 1(最一个字符不同) 或f[i][j] = f[i - 1][j + 1] (最一个字符相同)。

取三种情况的最小值，就是f[i][j]。

时间复杂度：
状态数量：n^2;
状态计算：3
o(n^2)

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;

char a[N],b[N];//字符串
int n,m;
int f[N][N];//状态转移方程

int main()
{
    cin>>n>>a+1;//字符串从下标1开始 省去一些边界问题的判断
    cin>>m>>b+1;
    
    for(int i=0;i<=m;i++) f[0][i]=i;//初始化
    for(int i=0;i<=n;i++) f[i][0]=i;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);//状态转移
            if(a[i]==b[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[n][m]<<endl;//字符串a[1~i]与b[1~j]所有操作方案的最小值
    
    return 0;
}