Global sequence alignment without mismatches ($D_{i,j}=\max (D_{i-1,j}-g,D_{i,j-1}-g,D_{i-1,j-1}+1\text{ if }{x}_i=y_j)$)

Align two complete strings using matching letters or a letter opposite a gap, with no unequal-letter columns and no double-gap columns. Give each match score one and each gap penalty $g\ge 0$. The dynamic programming table for prefixes starts with $D_{i,0}=-gi$ and $D_{0,j}=-gj$. Its last-column cases give the displayed recurrence, where the diagonal candidate is omitted on a mismatch. Construction takes $O(mn)$ time for positive lengths and $O(mn)$ space with full alignment traceback.

An alignment with $\ell$ matches has $m+n-2\ell$ gaps and score $(1+2g)\ell -g(m+n)$. Therefore a longest common subsequence determines its optimum. A finite mismatch penalty would solve a different problem.