Los estados bidimensionales suelen describir una posición física o dos prefijos consumidos. Una celda de una cuadrícula depende de sus vecinas. Un par de longitudes de prefijos de cadenas describe qué ediciones o intercalados siguen siendo posibles. Nombra las dos coordenadas antes de elegir la disposición de la tabla. Una fila móvil ahorra espacio solo cuando cada dependencia sigue apuntando a la fila antigua o nueva correcta.
Los estados límite hacen buena parte del trabajo. Las celdas bloqueadas borran recuentos de rutas, los prefijos de texto vacíos tienen costes de edición con sentido y las letras repetidas pueden dejar más de un intercalado válido. Una coincidencia voraz puede descartar el camino que necesitas después.
El último problema cambia la forma del estado a un intervalo. Elegir la última retirada dentro de un intervalo fija sus vecinas y separa el trabajo restante en partes izquierda y derecha independientes. Es el mismo hábito: elige un estado que deje bien definida la siguiente decisión y procesa primero las dependencias más pequeñas.
Construye estados sobre cuadrículas, prefijos de cadenas e intervalos abiertos.