Explain how dynamic programming is used in sequence alignment.

Dynamic programming in sequence alignment builds optimal alignments by breaking the problem into smaller subproblems. For two sequences of length m and n, it creates an (m+1) x (n+1) matrix where each cell (i,j) represents the best alignment score for the first i characters of sequence 1 and first j characters of sequence 2. Each cell is calculated from three possibilities: diagonal (match/mismatch), left (gap in sequence 2), and top (gap in sequence 1). Needleman-Wunsch (global) initializes edges with gap penalties and traces back from bottom-right. Smith-Waterman (local) allows zero scores and traces from highest-scoring cell. Time complexity is O(mn), space can be optimized to O(min(m,n)).