= Solution
Let $D_{i,j}$ be the optimal score for aligning the complete prefixes of lengths $i,j$. The boundary values and recurrence are
$$
D_{0,0}=0,\quad D_{i,0}=-gi,\quad D_{0,j}=-gj,
$$
$$
\boxed{D_{i,j}=\max\left\{D_{i-1,j}-g,\ D_{i,j-1}-g,\ D_{i-1,j-1}+1\ \text{only if }x[i-1]=y[j-1]\right\}.}
$$
The last candidate is omitted when the letters differ. Fill rows or columns in increasing index order and return \b[$D_{m,n}$]. The final-column cases in part (a) exhaust all legal alignments and each can be appended to an optimal smaller alignment, proving the recurrence by <induction> on $i+j$.
There are $(m+1)(n+1)$ entries and at most three constant-time candidates per interior entry. Thus the time is \b[$O(mn)$] for positive $m,n$, or $O(mn+m+n+1)$ including empty-input boundary cases, with the same full-table space bound. Computing only the score can reduce auxiliary storage to $O(\min(m,n)+1)$ by retaining two rows. This is <global sequence alignment without mismatches>; admitting a diagonal move on unequal letters would solve a different problem.
Back to article page
