Contest Duration: - (local time) (100 minutes) Back to Home

## 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: