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)\).

posted:
last update: