O padrão em 30 segundos
Programação dinâmica em uma dimensão: o resultado de hoje depende de poucos resultados anteriores. Fibonacci anabolizado: climbing stairs, house robber, coin change, longest increasing subsequence. A habilidade avaliada é DEFINIR o estado em voz alta.
Como reconhecer na hora
- "Quantas maneiras de..." ou "máximo/mínimo até a posição i"
- Decisão em cada passo que depende do que você decidiu antes
- Recursão com subproblemas repetidos → memoização → tabela
onde todo mundo erra · anotado no caderno
Pular direto pro código sem conseguir dizer "dp[i] significa X". Se você não fala a definição do estado em uma frase, o entrevistador já anotou o não. Comece pela recorrência bruta, memoize, depois itere. Mostre o caminho.
Complexidade típica: Tipicamente O(n) tempo; espaço O(n) que muitas vezes comprime pra O(1). Dizer isso rende ponto.
Os 12 problemas da categoria
| Problema | Dificuldade | Nível no app |
|---|---|---|
| Climbing Stairs cai muito | easy | nível 1 · core |
| Min Cost Climbing Stairs | easy | nível 1 |
| House Robber cai muito | medium | nível 2 · core |
| House Robber II | medium | nível 2 · core |
| Longest Palindromic Substring cai muito | medium | nível 2 · core |
| Palindromic Substrings | medium | nível 2 · core |
| Decode Ways | medium | nível 2 · core |
| Coin Change cai muito | medium | nível 2 · core |
| Maximum Product Subarray | medium | nível 2 · core |
| Word Break cai muito | medium | nível 2 · core |
| Longest Increasing Subsequence | medium | nível 2 · core |
| Partition Equal Subset Sum | medium | nível 3 |
No app, esses 12 problemas entram numa trilha de 4 níveis com marcação do que mais cai em entrevista, e você registra tentativa, revisão e domínio de cada um.
Abrir a trilha NeetCode no app