Programação Dinâmica — Memoização e Tabulação Explicadas

Programação dinâmica é uma forma de resolver problemas salvando respostas de subproblemas menores e reutilizando essas respostas depois. Ela ajuda quando os mesmos subproblemas aparecem de novo e a resposta completa pode ser construída a partir dessas respostas menores.

Os dois estilos principais são memoização e tabulação. A memoização armazena respostas durante uma solução recursiva. A tabulação preenche respostas em ordem bottom-up, geralmente com um array ou tabela.

Quando a programação dinâmica funciona

A programação dinâmica é útil quando duas condições são verdadeiras.

Primeiro, os subproblemas se sobrepõem. Isso significa que o mesmo resultado intermediário é necessário mais de uma vez. Segundo, respostas maiores podem ser construídas a partir de respostas menores de forma consistente.

Se essas condições não forem verdadeiras, armazenar resultados antigos pode aumentar o custo de memória sem ajudar muito.

Memoização vs. tabulação

Memoização: armazenamento top-down

A memoização começa com a ideia recursiva. Quando o algoritmo resolve um subproblema pela primeira vez, ele armazena o resultado. Chamadas posteriores reutilizam o valor armazenado em vez de recalculá-lo.

Esse estilo costuma ser mais fácil quando a recorrência está clara, mas a ordem de todos os estados necessários não está.

Tabulação: construção bottom-up

A tabulação começa pelos casos base e preenche os estados em uma ordem que torna as dependências disponíveis quando necessário.

Esse estilo costuma ser mais fácil quando você já conhece uma ordem de iteração clara e quer controle explícito sobre a tabela.

Exemplo de programação dinâmica: Fibonacci

A sequência de Fibonacci é definida por

$$F(0) = 0, \quad F(1) = 1$$

e, para $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Uma solução recursiva simples repete trabalho. Por exemplo, calcular $F(5)$ exige $F(4)$ e $F(3)$, e então calcular $F(4)$ exige $F(3)$ novamente. Essa chamada repetida de $F(3)$ é o tipo de desperdício que a programação dinâmica elimina.

Memoização em Fibonacci

Com memoização, a recorrência continua a mesma, mas cada valor é armazenado depois da primeira vez em que é calculado.

Para $F(5)$, a sequência útil é:

• calcular e armazenar $F(0)=0$
• calcular e armazenar $F(1)=1$
• calcular e armazenar $F(2)=1$
• calcular e armazenar $F(3)=2$
• calcular e armazenar $F(4)=3$
• calcular e armazenar $F(5)=5$

O ponto principal é que cada estado é calculado uma vez. Pedidos posteriores leem o valor armazenado.

Tabulação em Fibonacci

Com tabulação, você constrói a partir dos casos base para cima:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Essa versão deixa a ordem das dependências óbvia: cada novo valor usa entradas que já são conhecidas.

Por que a programação dinâmica pode ser mais rápida

Se um problema tem apenas $k$ estados distintos que importam, a programação dinâmica tenta resolver cada um desses $k$ estados uma única vez. Isso pode transformar uma grande árvore recursiva em um cálculo muito menor.

O ganho exato de velocidade depende do problema. Programação dinâmica não é automaticamente rápida. Ela ajuda quando o trabalho repetido é uma parte real da solução original.

Erros comuns em programação dinâmica

Usar quando os subproblemas não se sobrepõem

Nem todo problema recursivo é um problema de programação dinâmica. Se quase todo subproblema for diferente, armazenar resultados pode não economizar trabalho o suficiente para fazer diferença.

Definir o estado errado

O estado precisa incluir todas as informações necessárias para o próximo passo. Se faltar informação importante, a recorrência pode parecer válida, mas produzir respostas erradas.

Errar os casos base

Os casos base sustentam todo o método. Se os valores iniciais estiverem errados, todo estado posterior construído a partir deles também estará errado.

Preencher a tabela na ordem errada

A tabulação só funciona quando cada estado é preenchido depois dos estados dos quais ele depende. Uma recorrência correta ainda pode falhar se a ordem de preenchimento estiver errada.

Supor que programação dinâmica sempre significa otimização

Muitos exemplos famosos maximizam ou minimizam alguma coisa, mas a programação dinâmica também é usada para problemas de contagem e decisão. O verdadeiro sinal são subproblemas reutilizáveis, não a palavra "melhor".

Onde a programação dinâmica é usada

A programação dinâmica aparece em problemas como distância de edição, subsequência comum mais longa, contagem de caminhos, otimização no estilo mochila e alguns contextos de caminho mínimo.

Quando você estiver decidindo se deve tentar usá-la, faça duas perguntas:

• os subproblemas menores se repetem?
• a resposta maior pode ser construída a partir dessas respostas menores?

Se as duas respostas forem sim, a programação dinâmica é uma forte candidata.

Tente um problema parecido

Tente sua própria versão com o número de maneiras de subir $n$ degraus se cada movimento puder ser de $1$ degrau ou $2$ degraus. A recorrência é simples, os subproblemas repetidos são fáceis de identificar, e esse é um bom próximo exemplo depois de Fibonacci.