Why does BLAST use heuristics when dynamic programming can find the optimal alignment?

Why

Dynamic programming fills a matrix with one cell for each pair of positions in the two sequences. Each cell holds the best score of any alignment ending there, computed from its neighbors, so the best overall alignment is guaranteed under the chosen matrix and gap penalties. Needleman-Wunsch does this for global alignment and Smith-Waterman for local alignment.

Pearson's scoring matrix guide describes local alignments as rigorously calculated by Smith-Waterman and heuristically by BLASTP or FASTA. The cost is proportional to the query length times the database length, repeated for every search. BLAST avoids most of that work.

It looks for short word hits that score above a threshold, and extends only promising ones into full alignments. The gapped BLAST paper describes a new criterion for triggering extensions and a gapped heuristic that made the program about three times faster than the original. The price is that a real but weak similarity with no strong seed can be missed.

For most searches the loss is small, but for a critical distant relationship a rigorous search such as SSEARCH, or a profile method, is worth the time.