Subproblemas sobrepostos: a marca que pede a técnica

As duas marcas de um problema de DP

Antes de sair memoizando tudo, vale saber quando a técnica ajuda. Ela paga o custo da tabela justamente cortando trabalho repetido, então só faz sentido quando existe trabalho repetido para cortar. Essa é a primeira marca, os subproblemas sobrepostos: quando você quebra o problema em partes menores, as mesmas partes voltam a aparecer, de novo e de novo. No Fibonacci isso é gritante, porque fib de 3 é pedido por vários galhos. Contar de quantos jeitos dá para subir uma escada, calcular o troco de um valor com certas moedas, contar caminhos numa grade: todos escondem essa repetição.

A segunda marca é a subestrutura ótima: a resposta do problema grande se monta a partir das respostas de problemas menores. No Fibonacci, fib de n é literalmente a soma de dois fib menores. Na escada, o número de jeitos de chegar a um degrau é a soma dos jeitos de chegar aos degraus de onde você consegue dar o último passo. Quando as duas marcas aparecem juntas, repetição de pedaços e montagem a partir de pedaços, você está diante de um problema feito sob medida para memoização e programação dinâmica. Reconhecer isso é metade da solução.

Quando a técnica não serve

Confundir os casos é comum, então vale olhar o outro lado. Muitos algoritmos também quebram o problema em partes, mas sem repetição. A busca binária corta a lista pela metade e joga uma das metades fora; a metade que sobra é sempre nova, nunca revisitada. O merge sort divide a lista em duas e ordena cada uma, mas as duas metades são pedaços diferentes da lista, sem sobreposição. Nesses casos, uma tabela de resultados não teria o que reusar, porque nada se repete. Dividir para conquistar não é o mesmo que subproblemas sobrepostos: o primeiro quebra em pedaços novos, o segundo esbarra nos mesmos pedaços.

Um teste rápido de decisão

Na prática, dá para decidir com duas perguntas. Primeira: se eu quebrar esse problema em versões menores dele mesmo, os mesmos pedaços vão reaparecer? Se a resposta é sim, há subproblemas sobrepostos e a memoização tem o que cortar. Segunda: a resposta que eu quero se monta a partir das respostas dos pedaços menores? Se sim, há subestrutura ótima e dá para construir a solução por partes. Quando as duas respostas são sim, memoização e programação dinâmica entram em cena. Quando o problema quebra em pedaços sempre novos, ou quando o todo não se monta a partir das partes, procure outra técnica.