24 de Março
Maior subsequência comum
Como transformar a comparação entre duas strings em uma tabela de subproblemas em vez de repetir escolhas de recursao.
Programação Dinamica Intermediario 25 min TypeScript
Dadas duas strings text1 e text2, retorne o comprimento da maior subsequencia comum entre elas.
Se não existir subsequencia comum, retorne 0.
Exemplo:
Input: text1 = "abcde", text2 = "ace"
Output: 3
A maior subsequencia comum e "ace", com comprimento 3.
O que perceber antes de codar
- Subsequencia não precisa ser contigua.
- A resposta e um comprimento, não precisa reconstruir a string.
- Quando os caracteres não batem, a decisão vira "qual lado vale pular agora?".
Erros comuns
- confundir subsequencia com substring
- errar a definição de estado da tabela e se perder nos indices
Passo 1 - Não confundir subsequencia com substring
Aqui pode pular caracteres.
Isso significa que "ace" e subsequencia de "abcde", mesmo sem estar colada.
Se você pensar como substring, vai montar a solução errada.
Passo 2 - Escrever a versão inicial recursiva
A versão inicial natural e:
- olhar o primeiro caractere dos dois lados
- se forem iguais, conta 1 e anda nos dois
- se forem diferentes, tenta pular um lado ou o outro
Funciona.
Mas repete muitos subproblemas.
Passo 3 - Definir o estado certo
Uma definição boa e:
dp[i][j]= melhor resposta usando os primeirosicaracteres detext1e os primeirosjdetext2
Isso ajuda porque cada celula depende de subproblemas menores e bem definidos.
Passo 4 - Descobrir a transição
Se os ultimos caracteres batem:
dp[i][j] = dp[i - 1][j - 1] + 1
Se não batem:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
Essa e a regra central da tabela.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function longestCommonSubsequence(text1: string, text2: string): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(m * n)
Espaço: O(m * n)
Solução 1 - Recursao pura
Boa versão inicial para enxergar a lógica de escolha.
export function longestCommonSubsequence(text1: string, text2: string): number {
function dfs(index1: number, index2: number): number {
if (index1 === text1.length || index2 === text2.length) {
return 0
}
if (text1[index1] === text2[index2]) {
return 1 + dfs(index1 + 1, index2 + 1)
}
return Math.max(dfs(index1 + 1, index2), dfs(index1, index2 + 1))
}
return dfs(0, 0)
}Funciona, mas explode em retrabalho.
A etapa intermediaria seria memorizacao: guardar cada par (index1, index2) para não resolver o mesmo subproblema de novo.
Solução 2 - Programacao dinamica 2D
Agora cada subproblema e resolvido uma vez.
export function longestCommonSubsequence(text1: string, text2: string): number {
const rows = text1.length + 1
const cols = text2.length + 1
const dp = Array.from({ length: rows }, () => new Array(cols).fill(0))
for (let i = 1; i < rows; i += 1) {
for (let j = 1; j < cols; j += 1) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[text1.length][text2.length]
}O insight forte aqui e perceber que a recursao já estava te dando a formula. A programacao dinamica só organiza isso em tabela.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial recursiva compara os caracteres atuais. Se batem, eu conto 1 e ando nos dois. Se não batem, tento pular um lado ou o outro. O problema e o retrabalho. Entao eu transformo isso em programação dinamica 2D, onde
dp[i][j]guarda a melhor resposta para os primeirosiejcaracteres.
Isso mostra que você:
- separou bem subsequencia de substring
- conectou a recursão com a tabela
- explicou a transição sem decorar formula solta
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- comparar duas sequencias ao mesmo tempo
- preencher tabela 2D de subproblemas
- traduzir
recursaocom escolhas emprogramacao dinamicaiterativa
O ponto não e decorar esse problema.
O ponto e aprender a modelar subproblemas em duas dimensoes.