Padrão 4: DP em grid
Quando a DP tem duas dimensões, a tabela vira uma grade:
dp[r][c]. Cada célula se constrói a partir de células vizinhas já calculadas — e ver a tabela se preenchendo deixa a recorrência óbvia.
Tente primeiro: Unique Paths
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.
Um robô está no canto superior esquerdo de um grid m × n e quer chegar ao canto inferior direito, movendo-se só para baixo ou para a direita. Quantos caminhos distintos existem?
Exemplo: m = 3, n = 7 → 28.
Tentou? Contar todos os caminhos por força bruta (recursão sem cache) é exponencial. A teoria abaixo preenche uma tabela 2D em O(m·n).
A teoria: cada célula vem das vizinhas
No Unique Paths, o robô só se move para baixo ou para a direita.
Então, para chegar à célula (r, c), ele veio de cima (r-1, c) ou da
esquerda (r, c-1). O número de caminhos até (r, c) é a soma dos caminhos
até essas duas:
dp[r][c] = dp[r-1][c] + dp[r][c-1]
casos-base: 1ª linha e 1ª coluna = 1 (só há um caminho em linha reta)
Preencha a tabela linha por linha; cada célula usa a de cima e a da esquerda,
que já foram calculadas. Veja o grid dp se preenchendo, com o cursor na
célula atual:
A resposta é dp[m-1][n-1] — o canto inferior direito.
Por que é O(m·n)?
São m × n células (estados), cada uma calculada em O(1) (uma soma) →
O(m·n) de tempo, O(m·n) de espaço. De novo o "estados × custo": aqui o
número de estados é bidimensional. E, como cada linha só depende da anterior,
dá para reduzir o espaço a O(n) (guardar só uma linha) — a mesma ideia de
"só preciso dos últimos estados" da DP 1D.
A forma de toda DP em grid
Muitos problemas 2D seguem este molde, mudando só a recorrência e a operação:
| Problema | dp[r][c] significa | Recorrência |
|---|---|---|
| Unique Paths | caminhos até (r,c) | dp[r-1][c] + dp[r][c-1] |
| Minimum Path Sum | menor soma até (r,c) | grid[r][c] + min(cima, esquerda) |
| Maximal Square | lado do maior quadrado em (r,c) | 1 + min(cima, esquerda, diagonal) se '1' |
O método é o mesmo das outras DPs: o que dp[r][c] significa, de quais
células vizinhas depende e os casos-base (geralmente a primeira linha
e/ou coluna). A diferença é só a dimensão extra.
Conexão com a seção Matriz: lá você preencheu grids com travessias (espiral, DFS); aqui o grid é uma tabela de respostas que se constrói por recorrência. Mesma estrutura 2D, uso diferente.
🧠 Quiz de fixação
0/41. No Unique Paths, qual a recorrência e por quê?
2. Quais são os casos-base do Unique Paths?
3. Por que o Unique Paths é O(m·n) de tempo?
4. 'Menor soma de caminho do topo-esquerda ao fundo-direita num grid de custos.' Como adaptar?
Resumo
- DP em grid: tabela 2D
dp[r][c], cada célula vinda das vizinhas já calculadas. - Unique Paths:
dp[r][c] = dp[r-1][c] + dp[r][c-1], bordas = 1. - O(m·n) de tempo; espaço redutível a O(n) (uma linha).
- Molde igual ao das outras DPs, com uma dimensão a mais.
Próxima aula: comparar duas sequências numa tabela 2D — a DP de strings.