题解：AT_abc185_e [ABC185E] Sequence Matching

原题Link

题意

给定字符串 $A$ 和 $B$ ，可以插入，添加和删除。问最少次数。

Solution

一道 DP 裸题。

先设一下状态

设 $dp_{i,j}$ 表示串 $A$ 前 $i$ 个字符到串 $B$ 前 $j$ 个字符的最少次数。

看一看每一个 $dp_{i,j}$ 可以怎么得到：

如果当前有 $A_i=B_j$ 那么继承上一个状态，$dp_{i-1,j-1}$，直接由前面的状态就可以得到。

否则：

1. 可以由 $i-1$ 和 $j-1$ 的匹配情况加上一次修改操作。

2. 可以由 $i-1$ 和 $j$ 的匹配情况加上一次删除操作。

3. 可以由 $i$ 和 $j-1$ 的匹配情况加上一次添加操作。

所以状态转移方程就可以得出来了

$$dp_{i,j}=\min(dp_{i-1,j}+1,dp_{i,j-1}+1,dp_{i-1,j-1}+[a_i \ne b_j])$$

Code:

cpp
Copy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
string s1,s2;//初始字符串 
int l1,l2;
int dp[5000][5000];
int main()
{
      cin>>s1>>s2;
      l1=s1.length();
      l2=s2.length();
      memset(f,127,sizeof(f));
      //dp[i][j]表示把 s1前i位变为 s2的前j位的 最短编辑距离 
      for(int i=0;i<=l2;++i)
         dp[0][i]=i;
      for(int i=0;i<=l1;++i)
         dp[i][0]=i;
      for(int i=1;i<=l1;++i)
      {
             for(int j=1;j<=l2;++j)
             {
                     if(s1[i-1]==s2[j-1])
                        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);//上一位的基础上加"替换"
                     dp[i][j]=min(dp[i][j],dp[i][j-1]+1);//上一个的基础上加"添加"
                     dp[i][j]=min(dp[i][j],dp[i-1][j]+1);//上一位的基础上加"删除" 

             }
      }
      cout<<dp[l1][l2];
      return 0;
}