Muchas preguntas sobre cadenas comparan dos textos o cortan un texto en piezas, y las dos tienen la misma forma: la respuesta para un prefijo, o para un par de prefijos, depende de prefijos un poco más cortos. Define cell[i][j] como la respuesta para las primeras i letras de una cadena y las primeras j letras de la otra, escribe cómo se obtiene una celda a partir de sus vecinas y rellena la tabla fila a fila.
Con dos cadenas, un par de letras iguales extiende la celda diagonal, y un desajuste se queda con la mejor opción entre saltarse una letra de una cadena o de la otra. Para cortar una cadena, ok[end] o ways[end] mira hacia atrás todas las posiciones donde podría empezar la última pieza. Los problemas de conteo suman las formas de cada opción; los de optimización toman el mínimo o el máximo.
Dos hábitos ahorran tiempo en una entrevista. Di en una frase qué significa una celda antes de escribir código, y decide la fila base: el prefijo vacío suele tener exactamente una forma o un coste de cero. Cuando cada fila solo necesita la anterior, guarda dos filas y el espacio baja de O(nm) a O(m).
Una coincidencia extiende la diagonal; un desajuste conserva el mejor vecino.