Dynamic Programming: como Identificar o Problema antes de Atacar

O problema

Dynamic programming costuma ser ensinada do jeito mais hostil possível.

Mostram uma tabela.

Mostram uma relação de recorrência.

Mostram um código que parece funcionar por telepatia.

A pessoa até decora dois ou três problemas clássicos.

Mas, quando a pergunta muda de roupa, trava de novo.

O motivo é simples:

ela aprendeu a solução pronta, não aprendeu a reconhecer o tipo de problema.

Modelo mental

Dynamic programming serve para quando a solução ingênua resolve o mesmo pedaço do problema várias vezes.

Você percebe que:

• há subproblemas menores
• esses subproblemas se repetem
• a resposta de um estado pode ser reutilizada

Em frase curta:

DP é cache com critério sobre subproblemas repetidos.

Se não existe repetição relevante, provavelmente não é DP.

Se o estado não está claro, provavelmente você ainda não entendeu o problema.

Quebrando o problema

Pergunta 1: o que está sendo recalculado?

Esse é o melhor ponto de entrada.

Se a solução recursiva ingênua volta várias vezes para o mesmo cenário, apareceu um cheiro forte de DP.

Exemplos comuns:

• mesma posição no array com o mesmo contexto
• mesmo índice e mesma capacidade restante
• mesmo par de posições
• mesmo nó com mesmo orçamento, passos ou restrições

Pergunta 2: qual é o menor estado que importa?

Estado é a menor informação necessária para distinguir uma resposta de outra.

Esse ponto separa quem entendeu de quem só decorou.

Exemplo:

• se a resposta depende só do índice atual, o estado pode ser i
• se depende do índice e de uma capacidade restante, o estado pode ser (i, cap)
• se depende de duas strings em posições diferentes, o estado pode ser (i, j)

Se você coloca informação demais no estado, a solução fica pesada.

Se coloca informação de menos, a resposta fica errada.

Pergunta 3: como um estado nasce de estados menores?

Aqui entra a transição.

Você quer conseguir dizer algo como:

• “a resposta daqui depende da melhor escolha entre pegar e não pegar”
• “a resposta desta célula vem do melhor entre cima e esquerda”
• “a resposta deste ponto vem do menor custo entre os caminhos anteriores”

Se você não consegue explicar a transição em português simples, ainda não chegou na solução.

Pergunta 4: onde a recursão para?

Caso base não é detalhe.

É o que dá chão para todo o resto.

Sem caso base claro, a transição vira fórmula bonita em cima de nada.

Memoization vs tabulação

As duas técnicas implementam a mesma lógica.

Memoization costuma ser:

• top-down
• mais natural quando você pensa primeiro de forma recursiva
• boa para partir do raciocínio bruto e depois evitar repetição

Tabulação costuma ser:

• bottom-up
• boa quando a ordem dos estados está clara
• útil para reduzir overhead recursivo e controlar melhor espaço

Não são escolas rivais.

São dois jeitos de percorrer o mesmo mapa.

Exemplo simples

Pegue a pergunta:

Você pode subir uma escada dando 1 ou 2 passos por vez. De quantas formas diferentes chega ao topo?

Solução ingênua

Para chegar no degrau n, você pode vir de:

• n - 1
• n - 2

Então alguém escreve recursão pura.

O problema é que ways(n - 2) aparece várias vezes em ramos diferentes.

E ways(n - 3) também.

Logo, você está recalculando o mesmo subproblema sem necessidade.

O estado

Aqui o estado mínimo é só:

• o degrau atual n

A transição

A relação fica:

• ways(n) = ways(n - 1) + ways(n - 2)

O caso base

Algo como:

• ways(0) = 1
• ways(1) = 1

Pronto.

Agora já dá para resolver com memoization ou tabulação.

O ponto importante não é a escada em si.

É a lógica:

• subproblema repetido
• estado mínimo
• transição
• caso base

Onde muita gente se confunde

Confundir DP com backtracking

Backtracking explora escolhas e volta.

DP reaproveita resposta de estado.

Às vezes um problema pode até nascer de raciocínio recursivo parecido, mas a pergunta correta é diferente:

• preciso explorar combinações?
• ou só calcular melhor valor/quantidade/custo para estados repetidos?

Confundir DP com greedy

Greedy escolhe o melhor local esperando que isso feche globalmente.

DP compara possibilidades entre estados.

Se a escolha local não garante o global, forçar greedy costuma dar errado.

Sair montando tabela cedo demais

Esse é o erro mais comum.

A pessoa começa desenhando matriz sem ter definido o estado.

Aí a tabela vira decoração.

Como um senior pensa

Quem tem mais prática não começa por “isso é DP?”.

Começa por algo mais concreto:

• onde estou repetindo trabalho?
• o que distingue um subproblema do outro?
• se eu soubesse essa resposta antes, o que economizaria?

Esse jeito de pensar é mais robusto porque funciona fora da entrevista também.

No trabalho real, DP quase nunca aparece com esse nome.

Mas a ideia de:

• evitar recomputação
• modelar estado
• reaproveitar resultado parcial

aparece o tempo todo.

O que o entrevistador quer ver

Ele quer ver se você:

• reconhece repetição de subproblema
• define estado suficiente
• explica a transição sem fumaça
• escolhe uma implementação coerente

Se você disser com clareza “a solução recursiva repete cenários; vou guardar resposta por estado (i, j)”, já mostrou mais entendimento do que quem sai preenchendo tabela bonita sem explicar nada.

Dynamic programming não começa na tabela. Começa no desperdício.

Quando você enxerga o estado certo, metade do problema já ficou menor.