Caminhos Únicos e Soma Mínima de Caminho em Grades

Caminhos Únicos (LeetCode 62) pergunta: em uma grade m×n, quantos caminhos diferentes vão do canto superior esquerdo ao canto inferior direito se você só puder mover-se para a direita ou para baixo? Para uma grade 3×7, a resposta é 28. A ideia principal é que todo caminho até a célula (i,j) deve vir de (i-1,j) (acima) ou de (i,j-1) (à esquerda), o que fornece uma formulação natural de DP 2D.

Defina dp[i][j] = número de caminhos até a célula (i,j). A primeira linha e a primeira coluna são compostas apenas de 1s (há apenas uma maneira de chegar a qualquer célula da linha superior ou da coluna mais à esquerda). Para as outras células: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Preencha a tabela linha por linha; a resposta é dp[m-1][n-1]. Complexidade de tempo: O(m×n); espaço: O(m×n), redutível a O(n).

Como dp[i][j] depende apenas da linha atual e da linha anterior, você pode substituir a tabela 2D completa por um único vetor 1D. Inicialize todos os valores como 1 e, depois, para cada linha, atualize diretamente: dp[j] += dp[j-1]. Depois de processar a linha i, dp[j] contém o valor que correspondia a dp[i][j] na tabela 2D. Este é um padrão comum de otimização para problemas de DP 2D.

Caminhos Únicos II (LeetCode 63) adiciona obstáculos (células marcadas com 1) à grade. Qualquer caminho que passe por um obstáculo é inválido, portanto dp[i][j] = 0 se obstacle[i][j] == 1. Caso contrário, a recorrência é a mesma: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Se o início ou o fim estiver bloqueado, o resultado será imediatamente 0. Defina os casos base com cuidado — assim que aparecer um 1 na primeira linha ou coluna, todas as células subsequentes nessa linha ou coluna serão 0.

Soma Mínima de Caminho (LeetCode 64) pergunta: dada uma grade m×n preenchida com inteiros não negativos, encontre o caminho do canto superior esquerdo ao canto inferior direito que minimize a soma de todos os números ao longo do caminho (movendo-se apenas para a direita ou para baixo). Por exemplo, em [[1,3,1],[1,5,1],[4,2,1]], o caminho 1→3→1→1→1 produz soma 7. O estado de DP é o mesmo dos caminhos únicos, mas agora a recorrência usa o mínimo em vez da adição.

Defina dp[i][j] = custo mínimo para chegar à célula (i,j). Caso base: dp[0][0] = grid[0][0]. Primeira linha: dp[0][j] = dp[0][j-1] + grid[0][j] (a única maneira é vir da esquerda). Primeira coluna: dp[i][0] = dp[i-1][0] + grid[i][0] (a única maneira é vir de cima). Caso geral: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Esta é uma tradução direta do princípio da otimalidade.

Se você tiver permissão para modificar a grade de entrada, poderá atualizá-la no próprio lugar para evitar a alocação de uma tabela de DP separada. Isso reduz o espaço auxiliar para O(1) (além da entrada). Às vezes, entrevistadores perguntam sobre essa otimização — confirme se é permitido modificar a entrada antes de fazê-lo. Caso contrário, o truque do vetor deslizante 1D fornece espaço O(n) sem modificar a entrada.

Triângulo (LeetCode 120) solicita a soma mínima de um caminho do topo até a base em um vetor triangular, em que cada passo leva a um número adjacente na linha abaixo. A DP de baixo para cima é a abordagem mais simples: comece na penúltima linha e, para cada célula, adicione o mínimo das duas células diretamente abaixo. Isso evita acompanhar índices iniciais e faz a resposta subir naturalmente até o vértice.

Jogo da Masmorra (LeetCode 174) pergunta qual é a saúde inicial mínima necessária para resgatar uma princesa no canto inferior direito de uma grade com células negativas (dano) e positivas (cura). Você deve mover-se para a direita ou para baixo. O truque é preencher a tabela de DP de trás para frente (do canto inferior direito ao canto superior esquerdo), calculando a saúde mínima necessária em cada célula. Em cada célula: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). A saúde deve permanecer sempre em pelo menos 1.

Os problemas de DP em grades compartilham a mesma estrutura, mas diferem na direção do preenchimento e na operação de transição: Caminhos Únicos usa adição (conta todas as maneiras). Soma Mínima de Caminho usa o mínimo (otimiza). Jogo da Masmorra é preenchido de trás para frente (saúde necessária a partir do futuro). Ao abordar uma nova DP em grade, pergunte-se: (1) O que cada célula representa? (2) Em que direção devo preencher? (3) Qual operação combina as células vizinhas? Responder a essas três perguntas revela a solução completa.

Todos os problemas de DP em grade apresentados aqui têm complexidade de tempo O(m×n). O espaço varia de O(m×n) para uma tabela completa até O(n) com um vetor deslizante 1D e O(1) de espaço auxiliar quando a grade pode ser modificada no próprio lugar. Em entrevistas, mencione a otimização de espaço O(n) depois de apresentar a solução O(m×n) — isso demonstra que você conhece os compromissos envolvidos. Para todos os problemas, considere também se existe um atalho guloso, como a fórmula matemática para caminhos únicos.

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.

Nesta lição, você aprendeu: Caminhos Únicos preenche uma tabela 2D com dp[i][j] = dp[i-1][j] + dp[i][j-1] e pode ser calculado em O(1) usando combinatória, Soma Mínima de Caminho usa a mesma estrutura, mas substitui a adição por min para obter o custo ótimo do caminho e todos os problemas de DP em grades compartilham o padrão de definir um estado por célula e escolher um operador de transição (soma, mínimo, máximo). Em seguida, exploraremos a Maior Subsequência Comum usando DP 2D em duas sequências.