Muitas questões sobre strings comparam dois textos ou cortam um texto em partes, e as duas têm a mesma forma: a resposta para um prefixo, ou para um par de prefixos, depende de prefixos um pouco mais curtos. Defina cell[i][j] como a resposta para as primeiras i letras de uma string e as primeiras j letras da outra, escreva como uma célula decorre de suas vizinhas e preencha a tabela linha por linha.
Com duas strings, um par de letras iguais estende a célula diagonal, e uma divergência fica com a melhor opção entre pular uma letra de uma string ou da outra. Para cortar uma string, ok[end] ou ways[end] olha para trás todas as posições onde a última parte poderia começar. Problemas de contagem somam as formas de cada opção; os de otimização pegam o mínimo ou o máximo.
Dois hábitos economizam tempo em uma entrevista. Diga em uma frase o que uma célula significa antes de escrever código, e decida a linha base: o prefixo vazio costuma ter exatamente uma forma ou um custo de zero. Quando cada linha só precisa da anterior, guarde duas linhas e o espaço cai de O(nm) para O(m).
Uma correspondência estende a diagonal; uma divergência mantém o melhor vizinho.