Contagem de Caminhos em uma Grade

Você começa no canto superior esquerdo de uma grade e quer chegar ao canto inferior direito. Cada passo move-se para a direita ou para baixo. Quantos caminhos distintos existem?

Toda célula pode ser alcançada a partir da célula acima ou da célula à esquerda. Essa sobreposição é exatamente o motivo pelo qual este é um problema de DP.

Considere dp[i][j] como o número de maneiras de chegar à célula (i, j) a partir do início. Dar um nome claro ao estado é metade da batalha.

Você só chega vindo de cima ou da esquerda, portanto a contagem é a soma desses valores. Essa é a transição que conduz toda a tabela.

A célula inicial tem exatamente uma maneira de ser alcançada: não fazer nada. Portanto, dp[0][0] vale 1 antes que você preencha qualquer outra célula.

As células da linha superior ou da coluna esquerda têm uma única rota direta. A contagem delas é sempre 1, pois um dos vizinhos está fora da grade.

Crie uma tabela de m por n preenchida com zeros. Definir o tamanho antecipadamente mantém a indexação organizada e evita surpresas.

Percorra primeiro as linhas e depois as colunas, de cima para baixo e da esquerda para a direita. Essa ordem garante que ambos os vizinhos estejam prontos antes de serem usados.

Depois do preenchimento, a contagem de caminhos estará na última célula. A resposta é dp[m-1][n-1], o canto inferior direito.

Cada linha precisa apenas da linha acima, portanto você pode manter uma única linha e atualizá-la no próprio lugar. Isso reduz a memória para O(n).

Sem bloqueios, a resposta é um coeficiente binomial: escolha quais dos passos totais serão para baixo. A DP ainda é melhor quando surgem obstáculos.

Você está preenchendo dp[i][j] para uma célula interna livre. Qual fórmula está correta?

Defina dp como os caminhos até uma célula, atribua 1 a dp[0][0] e some a célula acima com a célula à esquerda. O canto contém a sua resposta. 🧭