DP: LCS y distancia de edición
¿Qué tan diferentes son dos strings? Una cuadrícula DP en 2-D sobre sus prefijos.
El motor detrás de diff, la corrección ortográfica y el alineamiento de ADN.
La cuadrícula: tres movimientos por celda
dp[i][j] = comparar los primeros i chars de A con los primeros j de B- Borrar (arriba+1) · Insertar (izquierda+1) · Coincidir/Sustituir (diagonal + 0 o 1)
- Base: vacío → prefijo = esa cantidad de inserciones/borrados
- LCS = la misma cuadrícula, la coincidencia extiende la diagonal, sin sustitución
Mira cómo se llena la cuadrícula
kitten → sitting. Verde azulado = diagonal gratis (chars iguales).
Camino naranja = el alineamiento: sub k→s, conservar itt, sub e→i, conservar n, +g. Distancia 3.
Exponencial → polinomial
Longitud 12: ingenua 42,000 llamadas, DP 169 celdas → 250× menos.
El alineamiento = un camino por la cuadrícula
- Todo camino de esquina a esquina es un alineamiento; costo = pasos que no son gratis
- diff = LCS de las líneas; ediciones = m + n − 2·LCS (sin sustitución)
- Secuencias largas: DP en banda, Hirschberg (espacio O(min)), semilla y extensión (BLAST)
- Arreglo rodante → espacio O(min(m,n)) si solo necesitas la distancia
Conclusión
Los problemas de secuencias son caminos-más-baratos por una cuadrícula.
Un solo diagrama le sirve a la teoría de códigos, a la biología y a la comparación de archivos.
Sigue: backtracking — buscar en el espacio de decisiones, podar los callejones sin salida.