902. 最短编辑距离

题意

输入两个字符串，可以将第一个字符串通过三种操作（删除，增加，修改）变成第二个字符串，问最小操作次数

输入

10
AGTCTGACGC
11
AGTAAGTAGGC

输出

4

数据范围

1≤n,m≤1000，表示的是字符串的长度

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int dp[N][N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,m;
    char a[N],b[N];
    
    cin>>n>>(a+1)>>m>>(b+1);
    
    for(int i=1;i<=n;i++)   dp[i][0]=i;
    for(int i=1;i<=m;i++)   dp[0][i]=i;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
            if(a[i]==b[j])  dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
            else    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    
    cout<<dp[n][m]<<endl;
    
    return 0;
}

总结

1.总体思路

该题是一个动态规划问题，y总讲解里面说深搜的时间复杂度会比较高，是因为遍历了每一种情况，而动态规划用一个数字表示了一类情况，所以时间复杂度会比较低，是一种感性的理解

集合的含义是，a字符串长度是i，变成长度是j的b字符串需要多少次操作

集合最后保留的是操作次数的最小值

状态转移方程和计算方法如下：分成三种情况，第一种情况是删除

2.删除

从a里面删除最后一个元素使得两个字符串相等，也就是说a的前面 i-1 个元素和b的前面 j 个元素是相等的，所以 dp [ i-1 ] [ j ] + 1 表示的就是删除的情况，+1表示删除这一步操作

3.增加

往a里面增加一个元素使得两个字符串相等，也就是说，增加的元素和b字符串的最后一个元素相等，那么原来a字符串的最后一个元素应该等于b字符串的倒数第二个元素，所以 dp [ i ] [ j-1 ] +1 表示的是增加一个元素的情况

4.更改

分为两种情况，两个字符串的最后一个元素是否相等

相等

dp [ i - 1 ] [ j - 1 ]
表示的是前面所有元素一一相等，最后一个元素也对应相等，不需要进行额外操作

不相等

在前面元素相等的基础上要加一，表示更改操作
dp [ i - 1 ] [ j - 1 ] + 1

5.遍历所有情况

取一个最小值就是我们需要的答案

6.初始化集合

dp数组在使用之前需要根据题意进行初始化，这里的初始化如下，表示假设一个字符串的字符串长度为0，那么需要的操作次数为另一个字符串的长度，要么是增加，要么是删除

	for(int i=1;i<=n;i++)	dp[i][0]=1;
	for(int i=1;i<=m;i++)	dp[0][m]=1;