Programação dinâmica passo a passo: derivando a distância de edição

Objetivo

Resolver, em tempo polinomial e com uso de memória previsível, um problema cuja resposta ótima é construída a partir de respostas ótimas para instâncias menores e cuja recursão ingênua recalcula as mesmas instâncias um número exponencial de vezes.

Pré-requisitos

Duas propriedades: subestrutura ótima (a melhor solução contém as melhores soluções dos subproblemas) e subproblemas sobrepostos (o número de subproblemas distintos é polinomial, enquanto a árvore de chamadas da recursão ingênua não é). O exemplo: a distância de edição entre as strings a (comprimento m) e b (comprimento n), isto é, o número mínimo de inserções, remoções e substituições de um único caractere necessárias para transformar a em b.

Passos

1. Defina o estado como o menor conjunto de parâmetros que identifica um subproblema: D(i, j) é a distância de edição entre os primeiros i caracteres de a e os primeiros j caracteres de b. A resposta é D(m, n).
2. Escreva os casos-base: D(i, 0) = i (remover tudo) e D(0, j) = j (inserir tudo).
3. Escreva a recorrência. Se a[i-1] == b[j-1], então D(i, j) = D(i-1, j-1). Caso contrário, D(i, j) = 1 + min(D(i-1, j), D(i, j-1), D(i-1, j-1)), em que os três termos correspondem a remoção, inserção e substituição.
4. Conte os estados: (m+1) * (n+1), cada um calculado em tempo constante a partir de três vizinhos, de modo que o algoritmo é O(mn). A recursão ingênua revisita D(i-1, j-1) a partir de três chamadores e explode em custo.
5. Aplique memoização top-down: escreva a recorrência literalmente como uma função recursiva e decore-a com @functools.cache (documentado em functools, junto com lru_cache). É a forma mais rápida de obter uma versão correta, mas a profundidade da recursão cresce com m + n, então serve para entradas curtas.
6. Tabule bottom-up: preencha uma tabela linha por linha, já que cada célula precisa apenas da linha acima e da célula à sua esquerda. Para kitten e sitting, a tabela termina com D(6, 7) = 3: substituir k por s, substituir e por i, inserir g.
7. Reduza a memória: mantenha apenas a linha anterior e a atual, o que dá espaço O(min(m, n)). Mantenha a tabela completa quando precisar do script de edição em si e faça o backtracking a partir de D(m, n).
8. Verifique contra força bruta em strings aleatórias pequenas, além de strings vazias, strings idênticas e diferenças de um único caractere.

Resultado esperado

Uma função com tempo quadrático e espaço linear, cuja recorrência está escrita em um comentário ao lado do código e foi conferida contra um oráculo de força bruta.

Limites e base de verificação

Problemas sem subestrutura ótima (o caminho simples mais longo em um grafo) não se resolvem com este método. Espaços de estados sobre subconjuntos são exponenciais no tamanho do conjunto e só são viáveis para entradas pequenas. Os valores do exemplo decorrem da recorrência por aritmética; nenhuma medição de tempo é afirmada.