Padrão 5: DP em sequências e strings
Comparar duas sequências (duas strings, dois arrays) é uma família clássica de DP: uma tabela 2D
dp[i][j]que relaciona um prefixo de cada uma. É o coração de problemas como subsequência comum, distância de edição e diff de arquivos.
Tente primeiro: Longest Common Subsequence
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dadas duas strings text1 e text2, retorne o comprimento da maior subsequência comum (caracteres na mesma ordem, não necessariamente contíguos).
Exemplo: "abcde" e "ace" → 3 (a subsequência "ace").
Tentou? Comparar todas as subsequências possíveis é exponencial. A teoria abaixo usa uma tabela 2D que cresce caractere a caractere, em O(m·n).
A teoria: dp[i][j] sobre dois prefixos
Defina dp[i][j] = a resposta considerando os primeiros i caracteres de
text1 e os primeiros j de text2. A recorrência olha o último
caractere de cada prefixo:
se text1[i-1] == text2[j-1]: # os últimos casam
dp[i][j] = dp[i-1][j-1] + 1 # usa esse par e resolve o resto
senão: # não casam: descarte um dos dois
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
casos-base: dp[0][*] = dp[*][0] = 0 (prefixo vazio)
A intuição: se os últimos caracteres são iguais, eles fazem parte da subsequência comum (some 1 e resolva o resto na diagonal). Se diferem, a melhor LCS ignora o último de uma das strings — pegue o melhor dos dois casos. A tabela é preenchida como um grid (DP 2D da aula anterior):
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3 ← dp[5][3] = 3 = LCS("abcde","ace")
Por que é O(m·n)?
São (m+1) × (n+1) estados, cada um O(1) → O(m·n) de tempo e espaço (o
espaço cai para O(n) guardando duas linhas). É a forma 2D do "estados × custo".
A família de DP em sequências
Tudo muda só a recorrência sobre dp[i][j]:
| Problema | dp[i][j] | Quando casam / não casam |
|---|---|---|
| Longest Common Subsequence | LCS dos prefixos | casam: diagonal+1; senão max(cima, esq) |
| Edit Distance | mín. edições | casam: diagonal; senão 1 + min(3 vizinhos) |
| Longest Increasing Subsequence | (1D) maior subseq. crescente até i | max(dp[j])+1 para j < i com nums[j] < nums[i] |
| Word Break | (1D) dá p/ quebrar s[0..i]? | algum corte j com dp[j] e s[j..i] no dicionário |
Note que LIS e Word Break são DP 1D sobre uma única sequência (cada posição olha para posições anteriores), enquanto LCS e Edit Distance são 2D (comparam duas sequências). O sinal: duas sequências para relacionar → tabela 2D; uma sequência com escolhas olhando para trás → tabela 1D.
Resumo
- DP em duas sequências: tabela 2D
dp[i][j]sobre os prefixos; a recorrência olha os últimos caracteres (casam → diagonal; senão → vizinhos). - LCS: casam →
dp[i-1][j-1]+1; senão →max(dp[i-1][j], dp[i][j-1]). O(m·n). - Uma sequência com escolhas para trás → DP 1D (LIS, Word Break); duas sequências → DP 2D (LCS, Edit Distance).
Última parada: a síntese da seção — e o fecho do curso inteiro.