Padrão 2: Incluir ou excluir
Uma família enorme de DPs se resume a uma decisão repetida: em cada item, pegar ou pular? A resposta ótima é o melhor entre as duas escolhas — e essa é a essência da DP de decisão.
Tente primeiro: House Robber
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Casas em fila, cada uma com um valor em nums. Você não pode roubar duas casas adjacentes. Retorne o máximo que dá para roubar.
Exemplo: [2,7,9,3,1] → 12 (roubar as casas 2, 9 e 1 → 2+9+1).
Tentou? A regra "não pode roubar casas adjacentes" cria a decisão: se roubo a casa i, não posso ter roubado a i-1. A teoria abaixo transforma isso numa recorrência simples.
A teoria: o melhor entre pegar e pular
No House Robber, ao chegar na casa i, há duas opções:
- Pular a casa
i: o melhor continua sendo o que você tinha atéi-1. - Roubar a casa
i: ganhanums[i], mas o melhor anterior permitido é o dei-2(não pode a adjacentei-1).
A resposta para i é o máximo dessas duas escolhas:
dp[i] = max(dp[i-1], # pular
nums[i] + dp[i-2]) # roubar
É o mesmo formato 1D da aula anterior, mas agora a recorrência exprime uma
decisão (max entre incluir e excluir). E, como só depende de i-1 e
i-2, dá para fazer com O(1) de espaço (dois acumuladores). Note o eco do
Kadane (Array): "estender ou recomeçar" também era uma decisão local — DP
sempre esteve por perto.
House Robber II: a casa em círculo
E se as casas formam um círculo (a primeira e a última são adjacentes)?
A sacada é reduzir ao problema que você já resolveu: ou você não rouba a
primeira casa, ou não rouba a última — então rode o House Robber linear
duas vezes (em nums[0..n-2] e em nums[1..n-1]) e pegue o maior. Reusar
a solução linear como peça é um padrão poderoso.
Greedy vs DP: a fronteira (Jump Game)
Nem todo problema de decisão precisa de DP — às vezes um guloso basta, e é mais barato. O Jump Game ("dá para chegar ao fim, dado que cada posição diz o salto máximo?") tem uma DP natural, mas um guloso O(n)/O(1) resolve: percorra rastreando a posição mais distante alcançável; se ela nunca fica para trás da posição atual, dá para chegar.
Quando preferir guloso a DP? Quando uma escolha local ótima leva à global (e dá para provar, como no argumento de troca da seção Intervalos). Quando não dá — quando você precisa comparar várias escolhas e lembrar resultados —, é DP. Na dúvida, DP é a rede de segurança: sempre funciona, ainda que às vezes faça mais trabalho que um guloso.
🧠 Quiz de fixação
0/41. Qual a recorrência do House Robber e o que cada parte significa?
2. No House Robber II (casas em CÍRCULO), como reusar a solução linear?
3. O Jump Game tem solução gulosa O(n). Quando um guloso pode substituir a DP?
4. Que padrão de uma seção anterior já era, na verdade, uma DP de decisão?
Resumo
- DP de decisão: em cada item, incluir ou excluir →
dp[i] = max(excluir, incluir). - House Robber:
max(dp[i-1], nums[i] + dp[i-2]), O(n)/O(1). - House Robber II: rode o linear duas vezes (sem a 1ª / sem a última).
- Greedy vs DP: guloso quando a escolha local garante o ótimo; DP quando precisa comparar e lembrar.
Próxima aula: compor um alvo a partir de itens reutilizáveis — knapsack.