Padrão 1: DP 1D (a recorrência)
A forma mais simples de DP: uma tabela unidimensional
dp[], onde cada entrada se constrói a partir de algumas anteriores. Dominar essa recorrência é a base de tudo que vem depois.
Tente primeiro: Climbing Stairs
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.
Você sobe uma escada de n degraus dando passos de 1 ou 2 degraus por vez. De quantas maneiras distintas dá para chegar ao topo?
Exemplo: n = 3 → 3 (1+1+1, 1+2, 2+1).
Tentou? Se você tentou recursão pura (
formas(n-1) + formas(n-2)), funciona mas recalcula os mesmos valores — exponencial. A teoria abaixo mostra como preencher uma tabela de baixo para cima, em O(n).
A teoria: construir a partir das respostas anteriores
No Climbing Stairs, para chegar ao degrau i você deu um último passo de 1
(vindo de i-1) ou de 2 (vindo de i-2). Logo o número de formas de chegar a
i é a soma das formas de chegar a esses dois:
dp[i] = dp[i-1] + dp[i-2]
casos-base: dp[0] = 1, dp[1] = 1
É a recorrência de Fibonacci! Em vez da recursão exponencial, preencha a tabela
dos casos-base para cima — cada dp[i] usa valores já calculados. Veja a
tabela dp preenchendo, com o cursor i lendo de i-1 e i-2:
Por que é O(n) — e como cair para O(1) de espaço
São n estados (dp[0..n]), cada um calculado em O(1) (uma soma) →
O(n) de tempo. A tabela ocupa O(n) de espaço, mas repare: dp[i] só
depende dos dois últimos valores. Então dá para jogar fora o array e
guardar só duas variáveis — O(1) de espaço:
anterior, atual = 1, 1
repita n-1 vezes:
anterior, atual = atual, anterior + atual
Essa redução ("só preciso dos últimos k valores") é um truque recorrente em DP 1D. Sempre olhe de quantos estados anteriores a recorrência depende.
A forma de toda DP 1D
O Climbing Stairs é o molde. Muitos problemas 1D seguem a mesma estrutura, mudando só a recorrência:
| Problema | dp[i] significa | Recorrência |
|---|---|---|
| Climbing Stairs | formas de chegar ao degrau i | dp[i-1] + dp[i-2] |
| House Robber | máximo roubando até a casa i | max(dp[i-1], nums[i] + dp[i-2]) |
| Min Cost Climbing | custo mínimo até o degrau i | cost[i] + min(dp[i-1], dp[i-2]) |
| Decode Ways | formas de decodificar até i | soma conforme 1 ou 2 dígitos válidos |
Todas: um estado por posição, recorrência olhando para trás, casos-base no
início. O segredo é descobrir o que dp[i] significa e de quais
anteriores ele depende.
🧠 Quiz de fixação
0/41. Por que a recursão ingênua do Climbing Stairs é lenta, e a DP resolve isso?
2. Qual a recorrência do Climbing Stairs e por quê?
3. Como o Climbing Stairs pode usar apenas O(1) de espaço?
4. Qual é o método para resolver uma DP 1D nova?
Resumo
- DP 1D: tabela
dp[]onde cada entrada se constrói das anteriores. - Climbing Stairs:
dp[i] = dp[i-1] + dp[i-2](Fibonacci), casos-basedp[0]=dp[1]=1. - O(n) de tempo; O(1) de espaço quando só os últimos k valores importam.
- Molde geral: defina o significado de
dp[i], a recorrência e os casos-base.
Próxima aula: quando cada item traz uma decisão — incluir ou excluir.