Estados bidimensionais costumam descrever uma posição física ou dois prefixos já consumidos. Uma célula de uma grade depende das vizinhas. Um par de comprimentos de prefixos de strings descreve quais edições ou intercalações ainda são possíveis. Nomeie as duas coordenadas antes de escolher o layout da tabela. Uma linha rolante só economiza espaço quando cada dependência continua apontando para a linha antiga ou a nova correta.
Os estados de borda fazem boa parte do trabalho. Células bloqueadas zeram as contagens de rotas, prefixos de texto vazios têm custos de edição significativos e letras repetidas podem deixar mais de uma intercalação válida. Uma correspondência gulosa pode descartar o caminho de que você vai precisar depois.
O último problema muda a forma do estado para um intervalo. Escolher a última remoção dentro de um intervalo fixa as vizinhas dela e separa o trabalho restante em partes esquerda e direita independentes. É o mesmo hábito: escolha um estado que deixe bem definida a próxima decisão e processe primeiro as dependências menores.
Construa estados sobre grades, prefixos de strings e intervalos abertos.