Programação Dinâmica¶

A programação dinâmica resolve problemas com subproblemas sobrepostos e subestrutura ótima avaliando cada estado relevante apenas uma vez.

Quatro etapas de projeto¶

Defina um estado com significado não ambíguo.
Derive uma recorrência a partir de estados menores.
Estabeleça casos-base e uma ordem válida de avaliação.
Reconstrua uma solução se apenas os valores forem insuficientes.

Comprimento da maior subsequência comum¶

Considere dp[i][j] como o comprimento da LCS dos prefixos left[0..i) e right[0..j).

dp[0][j] = dp[i][0] = 0
if left[i - 1] == right[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1]
otherwise: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

A tabela possui (m + 1)(n + 1) estados e trabalho Θ(1) por estado, o que resulta em tempo Θ(mn) e espaço Θ(mn). Se apenas o comprimento for necessário, duas linhas reduzem o espaço a Θ(min(m, n)).

Memoização versus tabulação¶

a memoização top-down avalia sob demanda os estados alcançáveis e usa recursão;
a tabulação bottom-up explicita a ordem das dependências e a redução de memória.

Erros comuns¶

um estado que omite informações necessárias a decisões futuras;
uma recorrência que permite combinações inválidas;
sobrescrever valores antes que todos os dependentes os consumam;
afirmar tempo polinomial sem contar as dimensões do estado.

Exercícios¶

Projete estados para a distância de edição.
Explique por que a recursão ingênua de Fibonacci repete trabalho.
Reconstrua uma LCS real a partir da tabela completa.