E - Sequence Matching Editorial by Feecle6418
We can use DP to solve this problem.
Let \(f(i,j)\) be the answer of the \(i\) first elements of \(A\) and \(j\) first elements of \(B\).
The we have:
- \(f(i,j)=\min(f(i-1,j)+1,f(i,j-1)+1,f(i-1,j-1)+[A_i\ne B_j])\ (i>0,j>0)\)
- \(f(i,j)=i+j\) \((i=0\) or \(j=0)\)
The answer is \(f(n,m)\). The time comlexity is \(O(nm)\).