O padrão em 30 segundos
DP com duas dimensões: comparar duas strings (edit distance, longest common subsequence) ou andar numa grade contando caminhos. A tabela dp[i][j] cruza prefixos, e a resposta mora no canto dela.
Como reconhecer na hora
- DUAS strings/sequências comparadas → dp[i][j] sobre prefixos
- Grade com movimento restrito (só direita/baixo) contando caminhos ou custo
- "Subsequência" comum/palíndroma entre duas coisas
Confundir subSTRING (contígua) com subSEQUÊNCIA (mantém ordem, pode pular): muda a recorrência inteira. E errar a linha/coluna base (casos com prefixo vazio), que é onde a tabela inteira ancora.
Complexidade típica: Em LCS e Edit Distance, O(n·m) tempo e espaço; para calcular apenas o valor da resposta, dá para usar O(min(n,m)) de espaço com duas linhas. Isso depende da recorrência: Burst Balloons usa DP de intervalos, com O(n³) tempo e O(n²) espaço; duas linhas não bastam porque um estado consulta vários subintervalos.
Os 11 problemas da categoria
| Problema | Dificuldade | Nível no VagaGringa |
|---|---|---|
| Unique Paths | medium | nível 2 · core |
| Longest Common Subsequence | medium | nível 2 · core |
| Best Time to Buy/Sell Stock With Cooldown | medium | nível 3 |
| Coin Change II | medium | nível 3 |
| Target Sum | medium | nível 3 |
| Interleaving String | medium | nível 3 |
| Edit Distance | medium | nível 3 |
| Longest Increasing Path in a Matrix | hard | nível 4 |
| Distinct Subsequences | hard | nível 4 |
| Burst Balloons | hard | nível 4 |
| Regular Expression Matching | hard | nível 4 |
No VagaGringa, esses 11 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