Síntese: qual padrão usar?
Cinco padrões de DP cobertos — e esta é a última seção do curso. Vamos fechar com a árvore de decisão de DP e, depois, um olhar sobre tudo que você construiu.
A árvore de decisão de DP
Reconheça a DP: há subproblemas que se REPETEM e a resposta se constrói dos menores?
1. Como modelar o estado?
├── uma posição numa sequência → dp[i] (DP 1D)
├── um valor-alvo a compor com itens → dp[a] (knapsack)
├── uma célula num grid → dp[r][c] (DP em grid)
└── prefixos de DUAS sequências → dp[i][j] (DP de strings)
2. Qual a recorrência (como dp se constrói dos estados menores)?
├── somar/contar caminhos → dp[i-1] + dp[i-2] / soma
├── decidir incluir ou excluir → max(excluir, incluir)
├── minimizar com itens reutilizáveis → min(dp[a-item] + 1)
└── comparar últimos elementos → casam? diagonal : vizinhos
3. Casos-base e ordem de preenchimento (dos menores para o maior).
E os reflexos da seção: tempo ≈ estados × custo por estado; quando a recorrência olha só os últimos k estados, reduza o espaço; e, antes de partir para DP, pergunte se um guloso já resolve.
O mapa completo da seção
| Padrão | Estado | Tempo |
|---|---|---|
| DP 1D | dp[i] (posição) | O(n) |
| Incluir/excluir | dp[i] = max(pular, pegar) | O(n) |
| Knapsack | dp[a] (valor-alvo) | O(alvo × itens) |
| DP em grid | dp[r][c] (célula) | O(m·n) |
| DP em sequências | dp[i][j] (prefixos) | O(m·n) |
A ideia-mãe: DP é recursão + memória. Defina o estado, a recorrência e os casos-base, e o resto é preencher uma tabela. O que parecia o tema mais assustador é, no fundo, o método mais sistemático do curso.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 6+ acertos: pronto para a prova final do curso.
🧠 Quiz da seção: Programação Dinâmica
0/61. 'Custo mínimo para subir uma escada, onde cada degrau cobra um custo (passos de 1 ou 2).' Qual padrão?
2. 'Dividir um array em dois subconjuntos de soma igual.' Qual padrão?
3. 'Distância de edição: mínimo de inserções/remoções/substituições para transformar uma string em outra.' Qual padrão?
4. 'Maior subsequência crescente num array.' 1D ou 2D, e por quê?
5. 'De quantas formas decodificar uma string de dígitos em letras (A=1..Z=26)?' Qual padrão?
6. Qual a forma mais rápida de estimar a complexidade de tempo de uma DP?
Você terminou o curso 🎉
Se você chegou até aqui, percorreu todos os tipos de problema do Top 75:
- Fundamentos (Big-O) e os padrões de Array e String — a base.
- Binary, Lista Ligada, Matriz, Intervalos — estruturas e técnicas.
- Árvores, Heap, Grafos — recursão e estruturas avançadas.
- Programação Dinâmica — onde tudo se junta.
E mais importante que os problemas: você treinou a forma de pensar — resolver no braço, achar o desperdício da força bruta, reconhecer o padrão e justificar a complexidade. Repare como os padrões conversam entre si: o hash map do Array reaparece em String e Grafos; o DFS/BFS atravessa Matriz, Árvore e Grafo; o Kadane já era DP. Não eram 75 problemas isolados — eram uns 20 padrões reaproveitados.
A prova final
A prova desta seção tem três problemas inéditos — Min Cost Climbing Stairs (fácil), Partition Equal Subset Sum (médio) e Edit Distance (difícil) — com casos ocultos. Depois dela, o melhor próximo passo é abrir o LeetCode e resolver problemas sem rede: agora você tem o mapa.
Boa prova — e parabéns por completar o curso! Volte para a página da seção e clique em "Prova final".