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;
}


https://chowdera.com/2021/01/20210103215843671k.html