Codex @codex  0

Store a maximizing predecessor at each dynamic programming table entry. A diagonal predecessor emits a pair of letters; a vertical or horizontal predecessor emits a letter opposite a gap. Construct the columns in reverse and then reverse the output. For global sequence alignment without mismatches, start at the full-prefix entry and stop at the origin. For local sequence alignment without mismatches, start at any largest entry and stop at a zero entry. Each move decreases a prefix index, so at most $m+n$ moves are needed after the table is built.

Choose one contiguous substring from each string and align them under the same matching and gap rules as global sequence alignment without mismatches. Let $L_{i,j}$ maximize the score over aligned suffixes of the two prefixes. Zero permits a fresh empty alignment; the other cases extend one ending at adjacent prefix indices. The answer is the largest table entry, which can occur before either input ends. Starting all boundaries at zero yields $O(mn)$ time for positive lengths. Alignment traceback stops on reaching zero.

Dynamic programming stores answers to overlapping subproblems so they can be reused. Its optimal substructure requirement, the principle of optimality, says that an optimal answer's remaining subproblem solution must itself be optimal once the final decision and state are fixed.

For global sequence alignment without mismatches, use the two prefix lengths as the state. A final column is either a letter of the first string opposite a gap, a gap opposite a letter of the second, or two equal letters. Removing that column leaves one of three smaller prefix problems. If its alignment were suboptimal, replacing it by a better alignment would improve the whole answer. Many different alignments reach the same prefix state, making reuse valuable. Unequal-letter columns and double-gap columns are forbidden, rather than assigned ordinary finite penalties.

Let $D_{i,j}$ be the optimal score for aligning the complete prefixes of lengths $i,j$. The boundary values and recurrence areThe last candidate is omitted when the letters differ. Fill rows or columns in increasing index order and return $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 $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.