Dynamic Programming

O que e

Dynamic programming, ou DP, e guardar e reaproveitar respostas de subproblemas para não recalcular tudo.

O nome parece mais complicado do que a ideia.

Muitas vezes e só:

“já resolvi essa parte antes, entao não preciso resolver de novo.”

Quando usar

Ela aparece quando duas coisas acontecem juntas:

• subproblemas se repetem
• a resposta maior depende dessas respostas menores

Erro comum

O erro clássico e decorar tabela sem entender de onde o estado veio.

Se você não sabe o que o estado representa, a técnica vira ritual.

Pergunta melhor

Antes de aplicar, vale perguntar:

1. qual e a menor decisão que se repete?
2. o que eu preciso lembrar para não recalcular?
3. estou pensando em estado e transição ou só em preencher tabela?