当前位置:网站首页>Luogu p2758 edit distance

Luogu p2758 edit distance

2021-01-07 21:47:39 zhb2000

subject

P2758 Edit distance

A typical linear DP topic .

Ideas

State definition

Linear dynamic programming like this , A common way to define States is : use \(f_i\) Express front \(i\) individual The elements meet the requirements ( Just think about the front \(i\) Elements ) The best answer is .

So it's natural for us to use \(f(i,j)\) It means that you will \(A[1..i]\) Convert to \(B[1..j]\) The minimum number of operations required ,\(f(n,m)\) It's the answer to the question (\(n,m\) Each represents a string \(A,B\) The length of ).

State shift

linear DP in , State transitions usually only need to consider And finally .

Imagine this scenario ,\(A[1..i]\) After several operations, it was changed to \(B[1..j]\), And The last step is Is in \(A\) At the end of On going . We can't help thinking of , There are only three possible operations in this last step :

  1. Delete \(A\) The character at the end ;
  2. stay \(A\) Insert a character at the end of ;
  3. modify \(A\) The character at the end .

So we found that , There are three strategies for \(A[1..i]\) It is amended as follows \(B[1..j]\)

  1. The first \(A[1..i-1]\) Become more like \(B[1..j]\) equally , And then delete \(A\) The character at the end ;
  2. The first \(A[1..i]\) Become more like \(B[1..j-1]\) equally , And then \(A\) Insert a character at the end of ;
  3. The first \(A[1..i-1]\) Become more like \(B[1..j-1]\) equally , Revise \(A\) The character at the end .

State transition :

\[f(i,j)=\min \left\{ \begin{aligned} f(i-1,j) & +1 \\ f(i,j-1) & +1 \\ f(i-1,j-1) & + \left\{ \begin{aligned} 0 & ,\textbf{if }A_i=B_j\\ 1 & ,\textbf{if }A_i \neq B_j \end{aligned} \right. \end{aligned} \right. \quad (i>0,j>0) \]

The boundary conditions

Observe state transition , Pay attention to the left to right Subscript change , The subscript is either unchanged , Or smaller , So the boundary is subscript \(0\) When :

\[\begin{aligned} f(0,j) & = j \\ f(i,0) & = i \\ f(0,0) & = 0 \\ \end{aligned} \]

Recursive order

Because subscripts from left to right are either unchanged , Or smaller , So the recursive order is from small to large \(i\) and \(j\).

Before you start recursion , Should be Let's find all the boundaries first Value .

Code

String subscript from 1 Start .

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2000 + 5;
char A[maxn];
char B[maxn];
int f[maxn][maxn];

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    scanf("%s%s", A + 1, B + 1);
    int n = strlen(A + 1);
    int m = strlen(B + 1);

    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        f[i][0] = i;
    for (int j = 1; j <= m; j++)
        f[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            f[i][j] = min(f[i - 1][j] + 1, min(f[i][j - 1] + 1, f[i - 1][j - 1] + (A[i] == B[j] ? 0 : 1)));

    printf("%d", f[n][m]);

    return 0;
}

版权声明
本文为[zhb2000]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210103215843671k.html