Programación dinámica paso a paso: derivación de la distancia de edición

Objetivo

Resolver un problema cuya respuesta óptima se construye a partir de respuestas óptimas a instancias más pequeñas, y cuya recursión ingenua recalcula las mismas instancias un número exponencial de veces, en tiempo polinómico y memoria predecible.

Requisitos previos

Dos propiedades: subestructura óptima (la mejor solución contiene las mejores soluciones a los subproblemas) y subproblemas superpuestos (el número de subproblemas distintos es polinómico, aunque el árbol de llamadas ingenuo no lo sea). El ejemplo: la distancia de edición entre las cadenas a (de longitud m) y b (de longitud n), el número mínimo de inserciones, eliminaciones y sustituciones de un solo carácter que convierten a en b.

Pasos

1. Definir el estado como el menor conjunto de parámetros que identifica un subproblema: D(i, j) es la distancia de edición entre los primeros i caracteres de a y los primeros j caracteres de b. La respuesta es D(m, n).
2. Escribir los casos base: D(i, 0) = i (eliminar todo) y D(0, j) = j (insertar todo).
3. Escribir la recurrencia. Si a[i-1] == b[j-1], entonces D(i, j) = D(i-1, j-1). En caso contrario, D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), siendo los tres términos la eliminación, la inserción y la sustitución.
4. Contar los estados: (m+1) * (n+1), cada uno calculado en tiempo constante a partir de tres vecinos, de modo que el algoritmo es O(mn). La recursión ingenua revisita D(i-1, j-1) desde tres llamadores y se dispara.
5. Memoizar de arriba hacia abajo: escribir la recurrencia tal cual como una función recursiva y decorarla con @functools.cache (documentado en functools junto a lru_cache). Esta es la forma más rápida de obtener una versión correcta, pero la profundidad crece con m + n, por lo que conviene a entradas cortas.
6. Tabular de abajo hacia arriba: llenar una tabla fila por fila, porque cada celda solo necesita la fila de arriba y la celda a su izquierda. Para kitten y sitting, la tabla termina con D(6, 7) = 3: sustituir k por s, sustituir e por i, insertar g.
7. Reducir la memoria: conservar solo la fila anterior y la actual, con lo que el espacio queda en O(min(m, n)). Conservar la tabla completa cuando se necesite el script de edición real y haya que retroceder desde D(m, n).
8. Verificar frente a fuerza bruta con cadenas aleatorias cortas, además de cadenas vacías, cadenas idénticas y diferencias de un solo carácter.

Resultado esperado

Una función con tiempo cuadrático y espacio lineal cuya recurrencia está escrita en un comentario junto al código, verificada frente a un oráculo de fuerza bruta.

Límites y base de verificación

Los problemas sin subestructura óptima (el camino simple más largo en un grafo) no se resuelven con este método. Los espacios de estado sobre subconjuntos son exponenciales en el tamaño del conjunto y solo son viables para entradas pequeñas. Las cifras del ejemplo se derivan de la recurrencia por aritmética; no se afirma ningún tiempo de ejecución.